algorithm - 动态编程硬币更改有限硬币

Question

动态规划找零问题(限币)。我正在尝试创建一个程序，将其作为 INPUT:

int coinValues[]; //e.g [coin1,coin2,coin3]
int coinLimit[]; //e.g [2 coin1 available,1 coin2 available,...]
int amount; //the amount we want change for.

输出:

int DynProg[]; //of size amount+1.

并且输出应该是一个大小为 amount+1 的数组，其中每个单元格代表我们需要为单元格索引的数量找零的最佳硬币数量。

示例:假设数组的单元格位于索引:5，内容为 2。这意味着，为了找零 5(INDEX)，您需要 2(cell's content) 个硬币(最优解)。

基本上我需要这个视频(C[p])的第一个数组的输出.这与 LIMITED COINS 的大DIFFERENCE 完全相同的问题。 Link to Video.

注意:看视频就明白了，忽略视频的第二个数组，记住我不需要组合，而是 DP 数组，这样我就可以找到找零的硬币。

谢谢。

Answer 1

考虑下一个伪代码:

for every coin nominal v = coinValues[i]:
    loop coinLimit[i] times:
        starting with k=0 entry, check for non-zero C[k]:
            if C[k]+1 < C[k+v] then
                  replace C[k+v] with C[k]+1 and set S[k+v]=v

清楚了吗？