理解变革的决策算法 [英] Understanding change-making algorithm

问题描述

我一直在寻找一个很好的解决了变化决策问题，我发现这code（蟒蛇）：

I was looking for a good solution to the Change-making problem and I found this code(Python):

target = 200
coins = [1,2,5,10,20,50,100,200]
ways = [1]+[0]*target
for coin in coins:
    for i in range(coin,target+1):
        ways[i]+=ways[i-coin]
print(ways[target])

我没有问题的理解是什么code字面上做，但我不明白为什么它的工作原理。 任何人都可以帮忙吗？

I have no problems understanding what the code literally does,but I can't understand WHY it works. Anyone can help?

推荐答案

要获取的元素等于A或B或C（我们的硬币），总结为'X'你所有可能的集可以：

To get all possible sets that elements are equal to 'a' or 'b' or 'c' (our coins) that sum up to 'X' you can:

• 在采取所有集，总结为Xa和添加一个额外的'a'到每个人。
• 在采取所有
集，总结为Xb和添加一个额外的B为每一个。
• 在采取所有
集，总结到XC和一个额外的C添加到每个之一。

• Take all such sets that sum up to X-a and add an extra 'a' to each one.
• Take all such sets that sum up to X-b and add an extra 'b' to each one.
• Take all such sets that sum up to X-c and add an extra 'c' to each one.

所以的方法可以得到X个是方法可以得到Xa和Xb和XC数的总和。

So number of ways you can get X is sum of numbers of ways you can get X-a and X-b and X-c.

ways[i]+=ways[i-coin]

休息是简单的复发。

Rest is simple recurrence.

额外提示： 在开始时，你可以得到完全的一种方式设置总和为零（空集）

Extra hint: at the start you can get set with sum zero in exactly one way (empty set)

ways = [1]+[0]*target

这篇关于理解变革的决策算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！