使用动态规划的硬币找零问题

Question

我一直在使用动态规划解决硬币找零问题。我尝试创建一个包含该索引所需的最小硬币数量的数组fin[]，然后打印它。 我编写了一段代码，我认为应该给出正确的输出，但我无法弄清楚为什么它没有给出精确答案。 例如：对于输入：4 3 1 2 3 （4是要更改的金额，3是可用硬币类型的数量，1 2 3是硬币值列表） 输出应该是：0 1 1 1 2（因为我们有1、2、3作为可用硬币，所以需要0个硬币来更改0，1个硬币来更改1，1个硬币来更改2，1个硬币来更改3，2个硬币来更改4） 但它给出的是0 1 2 2 2

以下是代码：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in= new Scanner(System.in);
        int ch = in.nextInt();
        int noc = in.nextInt();
        int[] ca = new int[noc];
        for(int i=0;i<noc;i++)
            {
                //taking input for coins available say a,b,c
            ca[i] = in.nextInt();
        }

       int[] fin = new int[ch+1]; //creating an array for 0 to change                                store the minimum number of coins required for each term at index

        int b=ch+1;
        for(int i=0;i<b;i++)
            {
            int count = i; //This initializes the min coins to that number so it is never greater than that number itself. (but I have a doubt here: what if we don't have 1 in coins available 

            for(int j=0; j<noc; j++)
                {
                int c = ca[j]; //this takes the value of coins available from starting everytime i changes

                if((c < i) && (fin[i-c] +1 < count)) // as we using dynamic programming it starts from base case, so the best value for each number i is stored in fin[] , when we check for number i+1, it checks best case for the previous numbers.
                    count = fin[i-c]+1 ;

            }
            fin[i]= count;
        }


        for(int i=0;i<b;i++)
            {
            System.out.println(fin[i]);
        }

    }
}

我参考了这个页面：http://interactivepython.org/runestone/static/pythonds/Recursion/DynamicProgramming.html 有人可以帮忙吗？

- G.tan

---

请解释输入和输出的含义，以及为什么您期望的输出是这样的。请注意在翻译过程中保持原意不变，并将其表述得通俗易懂。 - Hovercraft Full Of Eels

一个解释“找零钱”问题是什么的链接会很有帮助...这里有代码，但没有解释这个代码应该做什么:/ - fge

什么问题？ - shoover

Answer 1

你所引用的文章很好地解释了如何使用动态规划构建硬币找零算法。 该算法的Python版本可以翻译为Java：

import java.util.Arrays;
import java.util.List;

public class CoinChanger {

    public int[] dpMakeChange(List<Integer> coinValueList, int change, int[] minCoins) {
        for (int cents = 0; cents <= change; cents++) {
            int coinCount = cents;
            for (Integer c : coinValueList) {
                if (c > cents) {
                    continue;
                }
                if (minCoins[cents - c] + 1 < coinCount) {
                    coinCount = minCoins[cents - c] + 1;
                }
            }
            minCoins[cents] = coinCount;
        }
        return minCoins;
    }

    public static void main(String[] args) {
        List<Integer> coinValueList = Arrays.asList(new Integer[]{1, 2, 3});
        int change = 10;
        int[] minCoins = new int[change + 1];
        int[] result = (new CoinChanger()).dpMakeChange(coinValueList, change, minCoins);
        for (int i = 0; i < result.length; i++) {
            System.out.println("For change = " + i + " number of coins = " + result[i]);
        }
    }
}

使用面值为1、2和3的硬币，就像您的问题一样，先前的算法会给出正确的值：

For change = 0 number of coins = 0
For change = 1 number of coins = 1
For change = 2 number of coins = 1
For change = 3 number of coins = 1
For change = 4 number of coins = 2
For change = 5 number of coins = 2
For change = 6 number of coins = 2
For change = 7 number of coins = 3
For change = 8 number of coins = 3
For change = 9 number of coins = 3
For change = 10 number of coins = 4

- Ortomala Lokni