c++ - 输出所有组合的硬币找零算法是否仍然可以通过DP解决？

Question

比如总金额应该是5，我有1和2的硬币，那么有3种组合方式:

1 1 1 1 1
1 1 1 2
1 2 2

我看过一些关于如何使用动态规划或递归计算组合总数的帖子，但我想像上面的示例一样输出所有组合。我在下面提出了一个递归解决方案。

这基本上是一种回溯算法，我首先从最小的硬币开始并尝试获得总数，然后我删除一些硬币并尝试使用第二小的硬币......您可以在下面的 http://cpp.sh/ 中运行我的代码

在我的代码中，总数是 10，可用的硬币值是 1、2、5。

#include <iostream>
#include <stdlib.h>
#include <iomanip>
#include <cmath>
#include <vector>

using namespace std;


vector<vector<int>> res;
vector<int> values;
int total = 0;

void helper(vector<int>& curCoins, int current, int i){

    int old = current;

    if(i==values.size())
        return;

    int val = values[i];

    while(current<total){
        current += val;
        curCoins.push_back(val);
    }

    if(current==total){
        res.push_back(curCoins);
    }


    while (current>old) {
        current -= val;
        curCoins.pop_back();

        if (current>=0) {
            helper(curCoins, current, i+1);
        }
    }


}


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

    total = 10;
    values = {1,2,5};
    vector<int> chosenCoins;

    helper(chosenCoins, 0, 0);

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

    return 0;
}

是否有更好的解决方案来输出该问题的所有组合？动态规划？

编辑:

我的问题是这个问题可以用动态规划解决吗？

感谢您的帮助。我在这里实现了 DP 版本:Coin Change DP Algorithm Print All Combinations

Answer 1

DP 解决方案:

我们有

{solutions(n)} = Union ({solutions(n - 1) + coin1},
                        {solutions(n - 2) + coin2},
                        {solutions(n - 5) + coin5})

所以在代码中:

using combi_set = std::set<std::array<int, 3u>>;

void append(combi_set& res, const combi_set& prev, const std::array<int, 3u>& values)
{
    for (const auto& p : prev) {
        res.insert({{{p[0] + values[0], p[1] + values[1], p[2] + values[2]}}});   
    }
}

combi_set computeCombi(int total)
{
    std::vector<combi_set> combis(total + 1);

    combis[0].insert({{{0, 0, 0}}});
    for (int i = 1; i <= total; ++i) {
        append(combis[i], combis[i - 1], {{1, 0, 0}});
        if (i - 2 >= 0) { append(combis[i], combis[i - 2], {{0, 1, 0}}); }
        if (i - 5 >= 0) { append(combis[i], combis[i - 5], {{0, 0, 1}}); }
    }
    return combis[total];
}

Live Demo .