0

我在求和问题的递归解决方案中遇到问题。问题是：对于给定的 m 和 n，编写一个程序，将 n 个数字加总为 m，以便使用最小数字并且它们是。Id 有多个解决方案，正确的一个是使用更大数字的那个。用户输入 n,m 和 n 个数字。例如： m=19 n=4 8,5,4,1 。解决方案是 8+5+5+1。如果我用数组中的下一个数字调用函数并在其小于 sum 时添加它，则只有当数组中的下一个数字总和为 m 时才会找到解决方案。如果问题是这样的： m=28 n=3 8,7,5 解决方案是 8+8+7+5 但我的程序会去 8+8+8 并尝试添加 7 或 5 会崩溃，因为没有其中最多可以容纳 28 个。所以我在这里的问题是返回超过 2 个步骤。我可以从 8+8+8+7 到 8+8+8 但不能回到 8+8。这类似于背包问题，只是它更简单。抱歉到目前为止没有包括我的代码：

#include <iostream>
#include <vector>
using namespace std;

void outputt(vector<int>);

int x(int m,vector<int> s,int n,int u)
{
    static int sum=0;
    static int level=0;
    static vector<int> p;
    sum+=s[u];       
    p.push_back(s[u]);

    if(level==((n-u)+1))
    {
        p.pop_back();
        level=0;
        x(m,s,n,u-1);
    }

    if(sum>m)
    {
        level++;
        sum-=s[u];
        p.pop_back();
        x(m,s,n,u+1);
    }

    if(sum==m)
    {
        outputt(p);
        return sum;
    }
    else
        x(m,s,n,u);

    level++;
    if(level>n-1)
        outputt(p);

    if(sum==m)
        return sum;
    else
    {
        cout<<"....";
        x(m,s,n,level);
    }
}

void outputt(vector<int> x)
{
    for(vector<int>::iterator i=x.begin();i!=x.end();++i)
        cout<<*i<<" ";
}

int main()
{
    int m,n;
    cin>>m>>n;
    int z;
    vector<int> p;
    for(int i=0;i<n;++i)
    {
        cin>>z;
        p.push_back(z);
    }
    cout<<x(m,p,n,0);

    system("PAUSE");
}

输出有问题，但现在这并不重要。

4

2 回答 2

0

这离您需要的地方不远，这将尽快找到解决方案（最少的迭代），而不是最浅的解决方案。

#include <deque>
#include <iostream>
#include <iterator>
#include <algorithm>

template <typename IT, typename IT2>
bool perm_find(int num, IT start, IT last, IT2 output)
{
    for(IT first=start; first!=last; ++first)
    {
        int t=num-*first;
        if(t==0
        ||(t>0 && perm_find(t, start, last, output)))
        {   
            *output++=*first;
            return true;
        }   
    }
    return false;
} 

int main()
{
    int num;
    std::deque<int> pallet, results;

    std::cout << "Enter M: "      << std::endl;
    std::cin  >> num;
    std::cout << "Enter N vals: " << std::endl;

    std::copy(std::istream_iterator<int>(std::cin),
              std::istream_iterator<int>(),
              std::back_inserter(pallet));

    std::sort(pallet.rbegin(), pallet.rend());

    perm_find(num, pallet.begin(), pallet.end(), 
              std::back_inserter(results));

    std::copy(results.begin(), results.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    return 0;
}

要修改它以使其尽可能短，您需要使用 dijstras 算法之类的方法检查每个有效组合。

EDTT：我现在已经修复了一个错误

于 2012-03-09T12:02:44.647 回答
0

一些建议：

  • 避免递归代码中的静态（您可以将其用于调试），让函数的每个实例尽可能独立。
  • 遍历函数 (x) 中的所有数字 (s) 以回溯到最佳解决方案。
  • 将数字作为 const 引用传递，因为它们无论如何都不会改变。
  • 还传递（作为值）具有已选择数字（尝试）的容器，因此在返回时继续前一次尝试（回溯）。这应该是您的实际状态。
  • 总和是 std::accumulate(attempt.begin(), attempt.end(), 0);
  • 级别是尝试.size();
  • 首先对您的数字进行降序排序以获得最小的数字。
  • 如果您以后需要它，请返回尝试向量（现在您并不总是返回总和）。
于 2012-03-09T12:52:40.283 回答