現金分配邏輯 - Java

Question

假設我在貨幣的ArrayList中具有以下內容：（但不是按順序）。每個貨幣對象都有Bill和如下所示的計數。

$100 10 
$20 10 
$10 10 
$5 10 
$1 10 

如果我需要支付一定數額，您如何分配最低數量的賬單。 如果它被排序，那很容易。但是，如果沒有排序，那麼支付的有效方式是什麼？我嘗試與排序和它的作品。

什麼是支付的遞歸版本？

Answer 1

這可以通過動態編程完成。這是coin-change problem略有修改跟蹤當前硬幣剩餘的硬幣數量。

例如，

int coinChange(int[] bills, int[] count, int amount) { 
    int[][] solution = new int[bills.length + 1][amount + 1]; 
    for (int i = 0; i <= bills.length; i++) { 
     Arrays.fill(solution[i], Integer.MAX_VALUE); 
    } 
    solution[0][0] = 0; 
    for (int i = 1; i <= bills.length; i++) { 
     for (int j = 0; j <= amount; j++) { 
     if (solution[i - 1][j] != Integer.MAX_VALUE) { 
      for (int k = 0; k <= count[i - 1] && j + bills[i - 1] * k <= amount; k++) { 
      solution[i][j + bills[i - 1] * k] = 
       Math.min(solution[i - 1][j] + 1, solution[i][j + bills[i - 1] * k]); 
      } 
     } 
     } 
    } 
    return solution[bills.length][amount]; 
    } 

這可以遞歸公式表示爲：

i其中表示紙幣索引（索引），表示j量。對於i > 0，基本情況分別爲F(0, 0) = 1和F(0, i) = ∞，解決方案爲F(n, m)。當適當地記憶時，這減少到上述動態編程代碼。

追蹤確切的解決方案，而不是解決方案中的硬幣數量可以以現有的硬幣更換問題相同的方式完成，作爲練習留給讀者。