所有的解决方案来改变使得动态规划 [英] all solutions to change making with dynamic programming

问题描述

我检讨我的讲义为我们的算法类，我开始思考这个问题：

I was reviewing my handouts for our algorithm class and I started to think about this question:

由于不同类型的硬币不同的值，发现所有的硬币配置加起来一定款项，但不得重复。

在课堂上，我们解决了这个问题找到一个总和最少硬币数量的总和所有可能的方式的数量。但是，我们从来没有尝试过真正找到解决方案。

During class, we solved the problem to find the number of all possible ways for a sum and the least number of coins for a sum. However, we never tried to actually find the solutions.

我在想用动态规划解决这个问题。

I was thinking about solving this problem with dynamic programming.

我来用递归版本（为简单起见，我只打印解决方案）：

I came with the recursion version(for simplicity I only print the solutions):

void solve(vector<string>& result, string& currSoln, int index, int target, vector<int>& coins)
{
    if(target < 0)
    {
        return;
    }

    if(target == 0)
    {
        result.push_back(currSoln);
    }

    for(int i = index; i < coins.size(); ++i)
    {
        stringstream ss;
        ss << coins[i];
        string newCurrSoln = currSoln + ss.str() + " ";
        solve(result, newCurrSoln, i, target - coins[i], coins);
    }
}

然而，我被欲以DP到解决问题时卡住。 我有两个主要障碍：

However, I got stuck when trying to use DP to solve the problem. I have 2 major obstacles:

1. 在我不知道的数据结构，我应该用它来存储previous答案
2. 我不知道我的自下而上的方法（使用循环来替代递归）应该是什么样子。

任何帮助是值得欢迎的，有些codeS将AP preciated！

Any help is welcomed and some codes would be appreciated!

感谢您的时间。

推荐答案

在您生成一组中间状态的DP解决方案，以及许多方面也有到那里。那么你的答案是缠绕在成功状态时的数量。

In a dp solution you generate a set of intermediate states, and how many ways there are to get there. Then your answer is the number that wound up in a success state.

因此​​，对于改变计数的状态是，你必须改变的具体金额。计数是找零的方法的数量。而成功的状态所做的变化正确的金额。

So, for change counting, the states are that you got to a specific amount of change. The counts are the number of ways of making change. And the success state is that you made the correct amount of change.

这是计算解决方案，以枚举都需要保持这些中间状态去了，还保持记录所有转变为一个国家的每个状态 - 信息如何。 （在改变计数的情况下，怎么会被添加的硬币。）

To go from counting solutions to enumerating them you need to keep those intermediate states, and also keep a record in each state of all of the states that transitioned to that one - and information about how. (In the case of change counting, the how would be which coin you added.)

现在利用这些信息可以从成功的国家开始递归进入向后通过DP数据结构，真正找到解决方案，而不是数量。好消息是，所有的递归的工作是有效的 - 你总是只关注那些成功所以抓紧时间上的东西是行不通的路径。但是，如果有一个十亿的解决方案，那么就没有王室捷径，使打印出一个十亿的解决方案快。

Now with that information you can start from the success state and recursively go backwards through the dp data structures to actually find the solutions rather than the count. The good news is that all of your recursive work is efficient - you're always only looking at paths that succeed so waste no time on things that won't work. But if there are a billion solutions, then there is no royal shortcut that makes printing out a billion solutions fast.

如果你想成为一个小聪明，不过，你可以把它变成一个可用的枚举。你可以，例如，说：我知道有4323431的解决方案，什么是432134'th吗？并发现解决方案将是快速的。

If you wish to be a little clever, though, you can turn this into a usable enumeration. You can, for instance, say "I know there are 4323431 solutions, what is the 432134'th one?" And finding that solution will be quick.

这篇关于所有的解决方案来改变使得动态规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！