我试图用动态规划来解决一个问题,问题如下:
如果硬币(硬币、镍币、一角硬币、双一角硬币、四分之一硬币)的价值(1、5、10、20、25)是无限供应的,请找出最小数量的硬币来兑换65美分。使用了什么硬币(每个硬币多少枚)?说明使用动态规划算法所需的表格,以及如何获得所使用的硬币。
注:我不希望任何人为我演示整个表,但我有点拘泥于如何填写这个问题的表格。
我知道我的桌子看起来有点像这样:
5 10 15 20 25 30 35 40 45 50 55 60 65
1
5
10
20
25(我忽略了1,因为我知道这不是最好的解决方案)我最初的想法是,这张桌子会被填得有点像这样:
5 10 15 20 25 30 35 40 45 50 55 60 65
1
5 1 2 4 5 5 6 7 8 9 10 11 12 13
10 0 1
20
25当我要走得更远的时候我就被困在这里了。我认为我并不完全理解动态编程是如何解决这个问题的。我一直在读我的书,并在网上阅读,但我仍然有点困惑。
编辑:
感谢其中一个答案,这就是我如何想出解决方案的方法:
5 10 15 20 25 30 35 40 45 50 55 60 65
1
5 1 1 1 1
10 1 1 1 1
20 1 2 1 2
25 1 1 1 1 2 2 2 1发布于 2014-10-29 21:58:51
你做错了。列表示您必须返回的全部更改,行单元格表示所使用的某些硬币的数量(便士、镍、一角硬币、双一角硬币、四分之一硬币)。
该算法的全部目的是返回最小数量的硬币。例如,如果更改为25,您应该返回一个季度,而不是25美分。您可以看到,我在下面的表中使用了25美分列的四分之一。
在您的示例中,对于15项更改,您使用的是4x5美分,这是次优的,因为您可以使用一枚10美分的硬币和一枚5美分的硬币来返回总共15美分。在20美分栏中,您使用的是5x5美分的更改,这是不正确的,也不是最优的,因为您可以使用一枚20美分的硬币来返回20美分。
下面是为前5列填充的表。剩下的你可以补上:
5 10 15 20 25 30 35 40 45 50 55 60 65
1
5 1 1
10 1 1
20 1
25 1
--------------------------------------------------------
T 1 1 2 1 1我已经在底部添加了一个T行,以计算您用作零钱的硬币总数。你的目标是拥有一个。行中每列的可能编号。
发布于 2014-10-29 22:16:53
仍然使用动态规划,我将把问题建模为构造一个图,其中节点是金钱的数量(节点N为N美分),其中有5种类型的有向边,{1,5,10,20,25},对应于硬币类型。
保持一个尚未找到最优解的节点的运行前沿。每次迭代时,边界上最小的节点必须是最优的,这样就可以删除它,将多达5个新节点加到边界上。
下面是用于算法的Python:
def change(coins, target):
nodes = {0: (0, None)}
frontier = set([0])
while True:
n = min(frontier)
frontier.remove(n)
if n == target:
break
elif n > target:
return None # Infeasible!
count = nodes[n][0]
for coin in coins:
m = n + coin
frontier.add(m)
if not m in nodes or nodes[m][0] > count + 1:
nodes[m] = (count + 1, n)
m = target
sol = {}
while True:
n = nodes[m][1]
if n is None:
break
coin = m - n
sol[coin] = sol.get(coin, 0) + 1
m = n
return sol
print change([1, 5, 10, 20, 25], 65)输出为{25: 1, 20: 2}。
https://stackoverflow.com/questions/26641168
复制相似问题