最少投币算法

Question

我被硬币面额问题难住了。

我正试图找到最低数量的硬币用来弥补5.70美元（或570美分）。例如，如果硬币数组是{100,5,2,5,1}（100 x 10c硬币，5 x 20c，2 x 50c，5 x$1和1 x$2硬币），那么结果应该是{0,1,1,3,1}，此时硬币数组将由相同面额（$2,1,50c，20c，10c）组成

public static int[] makeChange(int change, int[] coins) {

    // while you have coins of that denomination left and the total
    // remaining amount exceeds that denomination, take a coin of that
    // denomination (i.e add it to your result array, subtract it from the
    // number of available coins, and update the total remainder). –

    for(int i= 0; i< coins.length; i++){
    while (coins[i] > 0) {

        if (coins[i] > 0 & change - 200 >= 0) {

            coins[4] = coins[4]--;
            change = change - 200;

        } else 

        if (coins[i] > 0 & change - 100 >= 0) {

            coins[3] = coins[3]--;
            change = change - 100;

        } else

        if (coins[i] > 0 & change - 50 >= 0) {

            coins[2] = coins[2]--;
            change = change - 50;

        } else

        if (coins[i] > 0 & change - 20 >= 0) {

            coins[1] = coins[1]--;
            change = change - 20;

        } else

        if (coins[i] > 0 & change - 10 >= 0) {

            coins[0] = coins[0]--;
            change = change - 10;

        }
    }

    }
    return coins;

}

我被困在如何从硬币数组中扣除值并返回它。

编辑：新代码

Answer 1

你走错方向了。此程序不会为您提供最佳解决方案。为了得到最优解，我们在这里实现并讨论了动态算法。请访问以下几个链接：

1. 链接1

Answer 2

维基百科的链接很少有关于如何决定像你这样的贪婪算法是否有效的细节。在这个问题中有一个更好的参考链接。本质上，如果硬币系统是规范的，贪婪算法将提供最优解。那么，[1,2,5,10,20]是规范的吗？（单位使用10美分，以便顺序从1开始）

根据本文，5硬币系统是非规范的当且仅当它恰好满足以下条件之一时：

• [1，c2，c3]是非规范的（对于[1，2，5]为false）
• 它不能写为[1,2,c3,c31,2*c3]（对于[1,2,5,10,20]为真）
• GreedAnswerSize（（k1）*c4）

因此，由于贪婪算法不会提供最佳答案（即使它提供了，我也怀疑它是否适用于有限的硬币），您应该尝试动态编程或一些开明的回溯：

import java.util.HashSet;
import java.util.PriorityQueue;

public class Main {

    public static class Answer implements Comparable<Answer> {
        public static final int coins[] = {1, 2, 5, 10, 20};

        private int availableCoins[] = new int[coins.length];
        private int totalAvailable;
        private int totalRemaining;
        private int coinsUsed;

        public Answer(int availableCoins[], int totalRemaining) {
            for (int i=0; i<coins.length; i++) {
                this.availableCoins[i] = availableCoins[i];
                totalAvailable += coins[i] * availableCoins[i];
            }
            this.totalRemaining = totalRemaining;
        }

        public boolean hasCoin(int coinIndex) { 
            return availableCoins[coinIndex] > 0; 
        }

        public boolean isPossibleBest(Answer oldBest) {
            boolean r = totalRemaining >= 0
                && totalAvailable >= totalRemaining
                && (oldBest == null || oldBest.coinsUsed > coinsUsed);
            return r;
        }

        public boolean isAnswer() {
            return totalRemaining == 0;
        }

        public Answer useCoin(int coinIndex) {
            Answer a = new Answer(availableCoins, totalRemaining - coins[coinIndex]);
            a.availableCoins[coinIndex]--;
            a.totalAvailable = totalAvailable - coins[coinIndex];
            a.coinsUsed = coinsUsed+1;
            return a;
        }

        public int getCoinsUsed() {
            return coinsUsed;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder("{");
            for (int c : availableCoins) sb.append(c + ",");            
            sb.setCharAt(sb.length()-1, '}');
            return sb.toString();
        }

        // try to be greedy first
        @Override
        public int compareTo(Answer a) {
            int r = totalRemaining - a.totalRemaining;
            return (r==0) ? coinsUsed - a.coinsUsed : r;
        }
    }        

    // returns an minimal set of coins to solve
    public static int makeChange(int change, int[] availableCoins) {
        PriorityQueue<Answer> queue = new PriorityQueue<Answer>();
        queue.add(new Answer(availableCoins, change));
        HashSet<String> known = new HashSet<String>();
        Answer best = null;
        int expansions = 0;
        while ( ! queue.isEmpty()) {
            Answer current = queue.remove();            
            expansions ++;
            String s = current.toString();
            if (current.isPossibleBest(best) && ! known.contains(s)) {
                known.add(s);
                if (current.isAnswer()) {
                    best = current;
                } else {
                    for (int i=0; i<Answer.coins.length; i++) {
                        if (current.hasCoin(i)) {
                            queue.add(current.useCoin(i));
                        }
                    }
                }
            }
        }
        // debug
        System.out.println("After " + expansions + " expansions");
        return (best != null) ? best.getCoinsUsed() : -1;
    }

    public static void main(String[] args) {
        for (int i=0; i<100; i++) {
            System.out.println("Solving for " + i + ":"
                + makeChange(i, new int[]{100,5,2,5,1}));
        }
    }
}

Answer 3

蛮力解决方案是尝试使用最高面值的硬币的可用数量（用完时停止，否则金额将变为负数），对于其中的每一个，使用不包括该面值的较短列表来解决剩余金额，并选择其中的最小值。如果基本情况是1c，则问题总是可以解决的，基本情况是返回n，否则它是n/d0（d0表示最小值），但必须注意在不可均匀整除时返回大值，以便优化可以选择不同的分支。可以通过剩余金额和下一个要尝试的面额进行参数化。因此，备忘表的大小应该是O（n*d），其中n是起始金额，d是面额数。

因此问题可以在伪多项式时间内得到解决。