贪心算法二维数组找零钱java

以下是使用贪心算法解决二维数组找零钱问题的Java代码：

public class CoinChange {
    public int coinChange(int[][] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int[] coin : coins) {
                if (i >= coin[0]) {
                    dp[i] = Math.min(dp[i], dp[i - coin[0]] + coin[1]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

其中，coins是一个二维数组，每个元素表示一种硬币的面值和数量。amount表示需要找的零钱总额。该算法的思路是，从小到大枚举需要找的零钱总额，对于每个总额，遍历所有硬币，找到能够凑出该总额的最小硬币数。最后返回凑出总额所需的最小硬币数。

相关问题

贪心算法找零钱java

以下是Java实现贪心算法找零钱的代码：

import java.util.Scanner;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.print("请输入需要找零的钱数：");
        int money = input.nextInt();
        int[] coins = {25, 10, 5, 1}; // 硬币面值
        int[] nums = new int[4]; // 硬币数量
        for (int i = 0; i < coins.length; i++) {
            nums[i] = money / coins[i];
            money = money % coins[i];
        }
        System.out.println("需要的硬币数量分别为：");
        for (int i = 0; i < coins.length; i++) {
            System.out.println(coins[i] + "美分：" + nums[i] + "个");
        }
    }
}

运行结果：

请输入需要找零的钱数：33
需要的硬币数量分别为：
25美分：1个
10美分：0个
5美分：1个
1美分：3个

贪心算法找零钱java算法设计分析

以下是贪心算法找零钱的Java实现及分析：

import java.util.Arrays;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 20, 50, 100};
        int money = 123;
        int[] result = new int[coins.length];
        for (int i = coins.length - 1; i >= 0; i--) {
            result[i] = money / coins[i];
            money %= coins[i];
        }
        System.out.println(Arrays.toString(result));
    }
}

上述代码中，我们定义了一个硬币数组`coins`和一个需要找零的金额`money`。我们使用一个`result`数组来记录每种硬币的数量。从硬币面额最大的开始，我们计算出当前硬币可以找零的最大数量，并将其记录在`result`数组中。然后我们将剩余的金额`money`对下一个面额的硬币进行同样的操作，直到所有硬币的数量都被计算出来。

这个算法的时间复杂度为O(n)，其中n是硬币的数量。因为我们只需要对每种硬币进行一次计算，所以这个算法的效率非常高。