Алгоритм изменения монет DP Распечатать все комбинации

Question

Классическая проблема замены монет хорошо описана здесь: http://www.algorithmist.com/index.php/Coin_Change

Здесь я хочу не только узнать, сколько существует комбинаций, но и распечатать их все. Я использую тот же алгоритм DP в этой ссылке в моей реализации, но вместо записи, сколько комбинаций в таблице DP для DP[i][j] = countЯ храню комбинации в таблице. Поэтому я использую трехмерный вектор для этой таблицы DP.

Я попытался улучшить свою реализацию, заметив, что при поиске таблицы требуется только информация из последней строки, поэтому мне не нужно всегда хранить всю таблицу.

Однако мое улучшенное решение 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();
    }
}