硬幣找零DP算法打印所有組合

Question

經典的硬幣找零問題以及描述如下：http://www.algorithmist.com/index.php/Coin_Change

在這裏，我想不僅知道有多少組合也有，但還打印出所有的人。在我的實現中，我在該鏈接中使用了相同的DP算法，但不是記錄DP表中DP[i][j] = count的多少個組合，而是將組合存儲在表中。所以我爲這個DP表使用了一個3D矢量。

我試着改進我的實現，注意到在查找表時只需要來自最後一行的信息，所以我並不需要總是存儲整個表。

但是，我改進的DP解決方案看起來還是很慢，所以我想知道下面的實現中是否存在一些問題，或者可以進行更多優化。謝謝！

您可以直接運行的代碼：

#include <iostream> 
#include <stdlib.h> 
#include <iomanip> 
#include <cmath> 
#include <vector> 
#include <algorithm> 
using namespace std; 

int main(int argc, const char * argv[]) {  

    int total = 10; //total amount 
    //available coin values, always include 0 coin value 
    vector<int> values = {0, 5, 2, 1}; 
    sort(values.begin(), values.end()); //I want smaller coins used first in the result 

    vector<vector<vector<int>>> empty(total+1); //just for clearing purpose 
    vector<vector<vector<int>>> lastRow(total+1); 
    vector<vector<vector<int>>> curRow(total+1); 


    for(int i=0; i<values.size(); i++) { 


     for(int curSum=0; curSum<=total; curSum++){ 
      if(curSum==0) { 
       //there's one combination using no coins    
       curRow[curSum].push_back(vector<int> {}); 

      }else if(i==0) { 
       //zero combination because can't use coin with value zero 

      }else if(values[i]>curSum){ 
       //can't use current coin cause it's too big, 
       //so total combination for current sum is the same without using it 
       curRow[curSum] = lastRow[curSum]; 

      }else{ 
       //not using current coin 
       curRow[curSum] = lastRow[curSum]; 
       vector<vector<int>> useCurCoin = curRow[curSum-values[i]]; 

       //using current coin 
       for(int k=0; k<useCurCoin.size(); k++){ 

        useCurCoin[k].push_back(values[i]); 
        curRow[curSum].push_back(useCurCoin[k]); 
       }    
      }  
     }   

     lastRow = curRow; 
     curRow = empty; 
    } 

    cout<<"Total number of combinations: "<<lastRow.back().size()<<endl; 
    for (int i=0; i<lastRow.back().size(); i++) { 
     for (int j=0; j<lastRow.back()[i].size(); j++) { 
      if(j!=0) 
       cout<<" "; 
      cout<<lastRow.back()[i][j]; 
     } 
     cout<<endl; 
    } 
    return 0; 
} 

Answer 1

看來你複製過多的載體：至少在過去else可以改寫爲

// not using current coin 
curRow[curSum] = lastRow[curSum]; 
const vector<vector<int>>& useCurCoin = curRow[curSum - values[i]]; // one less copy here 

// using current coin 
for(int k = 0; k != useCurCoin.size(); k++){ 
    curRow[curSum].push_back(useCurCoin[k]); 
    curRow[curSum].back().push_back(values[i]); // one less copy here too. 
} 

即使是可讀的清潔curRow = empty;，這可能會創建分配。 更好地創建一個功能

void Clean(vector<vector<vector<int>>>& vecs) 
{ 
    for (auto& v : vecs) { 
     v.clear(); 
    } 
}