动态编程硬币零钱 [英] Dynamic Programming Coin Change Limited Coins

问题描述

动态编程更改问题（有限硬币）。
我正在尝试创建一个程序，该程序以 INPUT：

int coinValues []; //例如[coin1，coin2，coin3]
int coinLimit []; //例如：[2个coin1可用，1个coin2可用，...]
int金额； //我们要更改的金额。

输出：

int DynProg []; //大小为+1。

输出应为大小为 amount + 1 的数组每个单元代表我们需要改变单元索引数量的最佳硬币数量。

And output should be an Array of size amount+1 of which each cell represents the optimal number of coins we need to give change for the amount of the cell's index.

示例：假设我们在索引：5处具有Array的单元格，其内容为2。
这意味着为了找零5（ INDEX ），您需要2（单元格内容）硬币（最佳解决方案）。

EXAMPLE: Let's say that we have the cell of Array at index: 5 with a content of 2. This means that in order to give change for the amount of 5(INDEX), you need 2(cell's content) coins (Optimal Solution).

基本上，我需要此视频（C [p]）
的第一个数组的输出。 受限硬币的大差异与完全相同。
链接到视频。

Basically i need exactly the output of the first array of this video(C[p]) . It's exactly the same problem with the big DIFFERENCE of LIMITED COINS. Link to Video.

注意：请看视频以理解，忽略视频的第二个数组，并记住我不需要组合，但需要DP数组，因此我可以找到要找零的硬币。

Note: See the video to understand, ignore the 2nd array of the video, and have in mind that i dont need the combinations, but the DP array, so then i can find which coins to give as change.

谢谢。

推荐答案

考虑下一个伪代码：

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

清楚吗？

这篇关于动态编程硬币零钱的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！