java - 计算一个数字的最大最佳面额组合

Question

问题陈述:

我需要获得给定数字的最佳面额组合。 示例:我有三个面额 {50,25,10}给定的数字是 30 那么列表应该返回 <10,10,10> .对于数字 80，它应该返回 <50,10,10,10>因为剩下的 30 不能完全除以 25。 对于 35，它应该返回 <25,10> 75 <50,25> 对于 65 <50,10>

这有点类似于硬币问题，但我无法获得面额的值(value)。

引用 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)完全可以被面额之一整除，这很有效，否则我根本不起作用。

Answer 1

一旦您在二维数组中找到了动态规划解的解，您就可以通过从末尾回溯数组 (arr[n][n]) 来找出最佳面额。