硬币找零（动态编程） [英] Coin Change (Dynamic Programming)

问题描述

对于硬币找零问题，我们通常具有以下重复关系：
（ P 是我们需要找零的总金额，而 d_i 是可用的硬币）

We usually the following recurrence relation for the coin change problem: (P is the total money for which we need change and d_i is the coin available)

但是我们不能这样做：
（ V 是给定的可用硬币分类集合， i 和 j 是其下标，其中 Vj 是给出的最高价值硬币）

But can't we make it like this: (V is the given sorted set of coins available, i and j are its subscripts with Vj being the highest value coin given)

C[p,Vi,j] = C[p,Vi,j-1]     if Vj > p
          = C[p-Vj,Vi,j] + 1  if Vj <=p

我写的东西有什么问题吗？尽管解决方案不是动态的，但是效率更高吗？

Is there anything wrong with what I wrote? Though the solution is not dynamic but isn't it more efficient?

推荐答案

考虑 P = 6，V = {4，3，1} 。您将选择 4，1，1 而不是 3，3 ，所以选择 3 个硬币，而不是最优的 2 。

Consider P = 6, V = {4, 3, 1}. You would pick 4, 1, 1 instead of 3, 3, so 3 coins instead of the optimal 2.

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