小编use*_*043的帖子

我试图通过扭曲来解决经典的动态编程硬币变化问题.这是一个家庭作业的问题,我不是在寻找完整的解决方案,只是为了指出我做错了什么.

输入:

• 量x,我们想在硬币支付一定的价值.
• 设定d面额的硬币可用(1C,5C,10C,25C,100C,200C)的代表数

输出:

• 需要交换手续付款的最小硬币数量.

假设:

• 收银机运营商拥有无限量的硬币供应,并知道如何进行最佳改变.

到目前为止我试图做的事情:

我正在尝试构建一个数组C,这样每个元素C [i],是最小/用于交换金额i的硬币数量.

C [0] = 0

对于C [i],我通过对所有可用的硬币面额采取最小的所有C [i-di]加1来计算它.然后我从可用的硬币中取出我挑选的硬币.

这种方法似乎在简单的情况下工作,但是当我有,例如:

99 99 0 0 0 1 0

我的方法失败了,因为它"便宜"到1美元,它将产生2个硬币的交换,而不是支付精确的99美分(交换99个硬币).

任何指针将不胜感激.