动态规划之最少硬币找零问题

小灰灰 2022-06-03 02:00 195阅读 0赞

> 假设有几种硬币，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。

private static final int MAX_VALUE = Integer.MAX_VALUE - 2;
    
        public static int coinChange(int[] coins, int change) {
            int[] seq = new int[change + 1];
            int[] sum = new int[change + 1];
            for (int i = 1; i <= change; i++) {
                sum[i] = MAX_VALUE;
            }
            sum[0] = 0;
            for (int i = 1; i < change + 1; i++) {
                for (int j = 0; j < coins.length; j++) {
                    if (i >= coins[j] && (1 + sum[i - coins[j]]) < sum[i]) {
                        sum[i] = 1 + sum[i - coins[j]];
                        seq[i] = j;
                    }
                }
            }
            int j = change;
            while (j > 0) {
                System.out.print(coins[seq[j]] + "\t");
                j = j - coins[seq[j]];
            }
            System.out.println();
            return sum[change];
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int[] coins = {
       2, 3, 4};
            System.out.println(String.format("coins is %s", Arrays.toString(coins)));
            while (in.hasNext()) {
                int change = in.nextInt();
                if (change == 0) {
                    break;
                }
                int coinNumber = coinChange(coins, change);
                System.out.println(coinNumber == MAX_VALUE ? 0 : coinNumber);
            }
        }

![这里写图片描述][SouthEast]

[http://www.edufyme.com/code/?id=33e75ff09dd601bbe69f351039152189][http_www.edufyme.com_code_id_33e75ff09dd601bbe69f351039152189]

[SouthEast]: /images/20220603/561d355befd84cc0908fe62e780475eb.png
[http_www.edufyme.com_code_id_33e75ff09dd601bbe69f351039152189]: http://www.edufyme.com/code/?id=33e75ff09dd601bbe69f351039152189