用贪心算法改变硬币

Question

伙计们，由于某种原因，我的贪婪硬币兑换程序不起作用。该函数应该 return 具有您可以更改值的最小硬币数量，并且还有一个数组，其中包含您可以为此使用的硬币。我的程序不显示任何内容，我不知道为什么。

public class Main {

public static int coinChangeGreedy(int[] coins, int n) {

        int result = 0;

        while (n != 0)
        {

            for (int i=coins.length - 1 ; i>=0 ; i--)
            {
                if (coins[i] <= n)
                {
                    n = n - coins[i];
                    result++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args)
    {
        int[] coins = {1, 2, 5};
        int n = 11;

        coinChangeGreedy(coins, n);

    }

}

Answer 1

好吧，起初 - 你没有打印任何东西 - 你只是运行函数。
其次 - 你的代码有一点缺陷。你看 - 如果你找到一个有效的硬币，你不应该去下一个硬币，而是再看看那个 "fits" 。
在您使用 n=11 的示例中。你有 5 作为第一个，然后移动到 2。但实际上你应该再次尝试 5（防止 for 循环转到下一个元素）。参见示例：

public static int coinChangeGreedy(int[] coins, int n) {

        int result = 0;

        while (n != 0) {

            for (int i=coins.length - 1 ; i>=0 ; i--) {
                if (coins[i] <= n) {
                    n = n - coins[i];
                  System.out.println("Adding " +coins[i]);
                  i++; //neutralizing i-- with i++.

                    result++;
                }
            }
        }
        return result;
    }

不，你会看到 5 被拿了两次。
P.s。 - 如果您假设硬币阵列将升序。要打印它，您只需执行：

System.out.println("Total coins needed: " +coinChangeGreedy(coins, n));

此外 - 如果您想跟踪使用的硬币，您可以在每次选择时将它们存储在 ArrayList 中。 list.add(coins[i]). And of course you declare and initialize thatlist` 在开头。

用贪心算法改变硬币

Coins Change with Greedy algorithm

java

greedy