理解變革的決策算法

我一直在尋找一個很好的解決了Change-making problem我發現這個代碼（蟒蛇）：理解變革的決策算法

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])

我的理解沒有問題了代碼字面上做，但我不能理解它爲什麼有效。任何人都可以提供幫助嗎？

來源

2013-02-21 gyosko

要獲得所有可能的集合的元素等於「A」或「B」或「C」（我們的硬幣），總計爲「X」，你可以：

採取所有集，總結到Xa併爲每一個添加一個額外的'a'。
把所有這些總和爲X-b的組合加到每一個上並加上一個額外的'b'。
把所有這些總和爲X-c的組合加到每一個上並加上一個額外的'c'。

所以你可以得到X的方法的數量是你可以得到X-a和X-b和X-c的方法總數。

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

休息是簡單的重複。

額外提示：在開始時，你可以在只有一個方式（空集）

ways = [1]+[0]*target

來源

2013-02-21 01:19:24 fsw

這是一個dynamic programming經典的例子得到設定總和爲零。它使用緩存來避免計數諸如 3 + 2 = 5兩次（因爲另一個可能的解決方案：2 + 3）的錯誤。遞歸算法陷入這個陷阱。我們來看一個簡單的例子，其中target = 5和coins = [1,2,3]。的代碼段你貼計數：

3 + 2
3 + 1 + 1
2 + 2 + 1
1 + 2 + 1 + 1
1 + 1 + 1 + 1個+ 1

而遞歸版本計數：

3 + 2
2 + 3
3 + 1 + 1
1 + 3 + 1
1 + 1 + 3
2 + 1 + 2
1 + 1 + 2
2 + 2 + 1
2 + 1 + 1 + 1
1 + 2 + 1 + 1
1 + 1 + 2 + 1
1 + 1 + 1 + 2
1 + 1 + 1 + 1 + 1

遞歸代碼：

coinsOptions = [1, 2, 3] 
def numberOfWays(target): 
    if (target < 0): 
     return 0 
    elif(target == 0): 
     return 1 
    else: 
     return sum([numberOfWays(target - coin) for coin in coinsOptions]) 
print numberOfWays(5)

動態規劃：

target = 5 
coins = [1,2,3] 
ways = [1]+[0]*target 
for coin in coins: 
    for i in range(coin, target+1): 
     ways[i]+=ways[i-coin] 
print ways[target]

來源

2013-02-21 01:38:10

代碼背後的主要思想是：「在每個步驟中有ways方法來改變i金額給予硬幣[1,...coin]「。

因此，在第一次迭代中，您只有面額爲1的硬幣。我相信顯而易見的是，只有一種方法可以讓任何目標只有這些硬幣。在此步驟ways陣列將看起來像[1,...1]（從0到target的所有目標只有一種方法）。

在下一步我們添加面額爲2的硬幣到上一組硬幣。現在我們可以計算出0到target之間每個目標的變化組合數量。顯然，組合的數量只會增加> = 2（或一般情況下添加新硬幣）。因此，對於目標等於2的組合數將爲ways[2](old) + ways[0](new)。一般來說，每當i等於推出新硬幣時，我們需要將1添加到之前的組合數，其中新組合將僅由一枚硬幣組成。

對於target>2，答案將包括「具有的target量的所有組合都小於coin硬幣」和「coin量的所有組合具有比coin本身少所有硬幣」的總和。

這裏我描述了兩個基本步驟，但我希望能夠很容易地推廣它。

讓我告訴你target = 4和coins=[1,2]的計算樹：

方法[4]給出幣= [1,2] =

方法[4]給出幣= [1] +方法[2]給出的硬幣= [1,2] =

1 +方式[2]給出的硬幣= [1] +方法[0]給定硬幣= [1,2] =

1 + 1 + 1 = 3

所以有三種方法可以進行更改：[1,1,1,1], [1,1,2], [2,2]。

上面給出的代碼完全等價於遞歸解決方案。如果您瞭解the recursive solution，我敢打賭你明白上面給出的解決方案。

來源

2013-02-21 01:39:02

您發佈的解決方案是此代碼的摘要版本。

/// <summary> 
    /// We are going to fill the biggest coins one by one. 
    /// </summary> 
    /// <param name="n"> the amount of money </param> 
    public static void MakeChange (int n) 
    { 
     int n1, n2, n3; // residual of amount after each coin 
     int quarter, dime, nickel; // These are number of 25c, 10c, 5c, 1c 
     for (quarter = n/25; quarter >= 0; quarter--) 
     { 
      n1 = n - 25 * quarter; 
      for (dime = n1/10; dime >= 0; dime--) 
      { 
       n2 = n1 - 10 * dime; 
       for (nickel = n2/5; nickel >= 0 && (n2 - 5*nickel) >= 0; nickel--) 
       { 
        n3 = n2 - 5 * nickel; 
        Console.WriteLine("{0},{1},{2},{3}", quarter, dime, nickel, n3); // n3 becomes the number of cent. 
       } 
      } 
     } 
    }

來源

2017-04-12 22:12:48 Aaron

理解變革的決策算法

回答

相關問題