首页 文章

最小硬币自上而下的解决方案没有给出预期的结果

提问于
浏览 次
1

我们有一个实习生使用自上而下的方法解决最小硬币问题 . 问题陈述给出一组硬币，返回形成总和所需的最小硬币 . 另外返回形成总和的硬币 .

Eg: coins = {7, 3, 2, 6}, total = 13,
result should be minCoins = {2}, coinsUsed = {7,6}

这是代码

package dp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class MinimumCoin {

    public static void main(String[] args) {

        int total = 13;
        int coins[] = {7, 3, 2, 6};

        Result rs  = minCoin(coins, total, new HashMap<>());
        System.out.println(rs.min);
        System.out.println(rs.coins);

    }

    public static Result minCoin(int[] coins, int total, Map<Integer, Result> memo) {

        if (total == 0) {
            return new Result();
        }

        if (memo.containsKey(total)) {
            return memo.get(total);
        }

        int min = Integer.MAX_VALUE;
        List<Integer> coinsSoFar = new ArrayList<>();

        for (int i = 0; i<coins.length; i++) {

            if (coins[i] > total) {
                continue;
            }

            Result rs = minCoin(coins, total-coins[i], memo);
            coinsSoFar.add(coins[i]);
            if (rs.min > min) {
                min = rs.min;
                coinsSoFar.addAll(rs.coins);
            }
            else {
                coinsSoFar.remove(coinsSoFar.size()-1);
            }
        }

        min =  (min == Integer.MAX_VALUE ? min : min + 1);

        Result rs = new Result(min, coinsSoFar);

        memo.put(total, rs);
        return rs;
    }

    public static class Result {

        private int min;
        private List<Integer> coins = new ArrayList<>();

        private Result() {}
        private Result(int min, List<Integer> coins) {
            this.min = min;
            this.coins = coins;
        }


    }
}

代码看起来很好 . 但不会返回预期的结果 . 当使用上面的输入执行时，程序返回INT.MAX作为minCoins并且列表为空 .

代码出错的任何提示？谢谢

java algorithm dynamic-programming coin-change

1 回答

  • 3

    好吧，你初始化 min 到 Integer.MAX_VALUE ，然后有以下代码：

    if (rs.min > min) {
    min = rs.min;
    coinsSoFar.addAll(rs.coins);
}

    如您所见， rs.min 是 int ，永远不会大于 min （ Integer.MAX_VALUE ） .

    您更改 min 的唯一其他地方如下：

    min =  (min == Integer.MAX_VALUE ? min : min + 1);

    但是，因为 min 仍然是 Integer.MAX_VALUE ，它永远不会改变 . 我会让你从这里拿走它 .

    回复于

相关问题