动态规划-给定金额所需的最小硬币数

Question

在研究硬币更换问题后，我尽力实施解决方案。到目前为止，我的代码打印了给定金额所需的最低硬币数量。然而，它并不打印出每种硬币面额所需的数量。这是我的代码目前的样子：

public class Coins {

    static int minCoins(int coinValues[], int m, int target) {
       int[] totalCoins = new int[target + 1];
       int[][] numOfCoins = new int[target + 1][m];

       totalCoins[0] = 0;

       for (int i = 1; i <= target; i++) {
           totalCoins[i] = Integer.MAX_VALUE;
       }

       for (int i = 1; i <= target; i++) {
           for (int j = 0; j < m; j++) {
               if (coinValues[j] <= i) {
                   int previous = totalCoins[i - coinValues[j]];
                   if (previous != Integer.MAX_VALUE && previous + 1 < totalCoins[i]) {
                       totalCoins[i] = previous + 1;
                   }
               }
           }
       }

       return totalCoins[target];
    }

    public static void main(String args[]) {
       int coinValues[] =  {1, 5, 10, 20};
       int m = coinValues.length;
       int target = 26;
       System.out.println("Minimum coins required is "+ minCoins(coinValues, m, target) );
    }
}

我只是很困惑如何/在哪里填充numOfCoins[]。

Answer 1

@user1523236提供了不能解决一般情况的贪婪方法。例如，如果去掉1面额并计算8的变化。

请看一下，比如4.12。动态规划，或CMP的动态规划算法（变更问题）。这两个参考文献都提供了通用的动态编程算法。

Answer 2

我在Groovy中使用欧元面值实现的解决方案

class coinage {

def denoms = [1, 2, 5, 10, 20, 50, 100, 200]
def resultArray = []
def remainder
def largest
def newResult

def calculate(int amt) {
    def value = denoms.findAll({ element -> element <= amt})
    largest = value.last()
    resultArray.add(largest)
    remainder = amt - largest

    if (remainder == 0 || remainder == amt) {
        newResult = resultArray.size()
        println("Minimum number of coins required for this is: $newResult")
    } else
        calculate(remainder)
}

}

并称之为：

coins = new coinage()
coins.calculate(305)