递归最大数目求和

我遇到了求和问题的递归求解问题。问题是：对于一个给定的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个。所以我的问题在这里有两个以上的步骤。我可以从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"); 
}

没有与输出一个问题，但现在不是很重要。

来源

2012-03-09 Transcendental

我们可以看到你的代码到目前为止吗？ – 2012-03-09 10:39:18

我认为你的问题陈述不是你的意思：“制作一个程序，将n个数字总和为m，以便使用最小数字”你的意思是：“从一组n个数字中抽取加数，最多为m，加数最少“ – 2012-03-09 11:09:50

男人，这是为IOCCC实际打算的作业吗？当他们真正阅读你的代码（和问题）时，人们更可能帮助你。 – 2012-03-09 12:04:55

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

#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-09 12:02:44 111111

谢谢，帮助我很多：D – Transcendental 2012-03-09 19:21:50

@Irrational兄弟没问题 – 111111 2012-03-09 19:33:58

一些建议有固定的一个错误：在递归码

避静（你可以用它进行调试），让该函数的每个实例是为尽可能独立。
循环遍历函数（x）中的所有数字以回溯到最优解。
传递数字作为常量引用，因为它们不会改变。
也传递（作为值）与已经选择的数字（尝试）的容器，所以当返回时继续前面的尝试（回溯）。这应该是你的实际状态。
总和是std :: accumulate（attempt.begin（），attempt.end（），0）;
该级别是attempt.size（）;
首先将您的数字降序得到最小数字。
如果您稍后需要它，则返回尝试向量（现在您并不总是返回总和）。

来源

2012-03-09 12:52:40 stefaanv

递归最大数目求和

回答

相关问题