问题陈述：
我需要获得给定数字的最佳面额组合 . 示例：我有三个面额 {50,25,10} ，给定数字为30，然后列表应返回 <10,10,10> . 对于数字80，它应该返回 <50,10,10,10> ，因为剩余的30不会完全除以25.对于35它应该返回 <25,10> 为75 <50,25> 为65 <50,10>
这有点类似于硬币问题，但我无法获得面额的 Value .
Refence StackOverFlow Coin change DP solution to keep track of coins这是我到目前为止所尝试的：
public static int[] minChange(int[] denom, int changeAmount) {
int n = denom.length;
int[] count = new int[changeAmount + 1];
int[] from = new int[changeAmount + 1];
count[0] = 1;
for (int i = 0; i < changeAmount; i++ )
if (count[i] > 0)
for (int j = 0; j < n; j++ ) {
int p = i + denom[j];
if (p <= changeAmount) {
if (count[p] == 0 || count[p] > count[i] + 1) {
count[p] = count[i] + 1;
from[p] = j;
}
}
}
// No solutions:
if (count[changeAmount] == 0)
return null;
// Build answer.
int[] result = new int[count[changeAmount] - 1];
int k = changeAmount;
while (k > 0) {
result[count[k] - 2] = denom[from[k]];
k = k - denom[from[k]];
}
return result;
}
如果 Value 完全可以被其中一种面额整除，那么这种方法很有效 .
1 回答
一旦在动态编程解决方案的2D数组中获得了解决方案，就可以通过从末尾回溯数组来找出最佳面额（arr [n] [n]） .