现金分配逻辑 - 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)。当适当地记忆时，这减少到上述动态编程代码。

追踪确切的解决方案，而不是解决方案中的硬币数量可以以现有的硬币更换问题相同的方式完成，作为练习留给读者。