遞歸最大數目求和

我遇到了求和問題的遞歸求解問題。問題是：對於一個給定的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

遞歸最大數目求和

回答

相關問題