leetcode322零钱兑换（背包问题）

目录

题目

背包状态转移方程

0-1背包

完全背包

解决方案

---

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

背包状态转移方程

0-1背包

weight[]={1,3,1} 表示物品的重量，value[] ={15,30,20}表数物品的价值，  求背包承受重量是maxWeight  = 4时，这个背包能够装的重大价值。

dp[i][j]表示，前i个物品，重量为j时的最大价值。

0-1背包dp[i][j]求值可以转换成2种情况

{ 

 dp[i-1][j]   第i个物品不放入背包的价值

dp[i-1][j-weight[i]]+value[i]   第i个物品放入背包的价值

}

(1)转移方程

  二维数组

dp[i][j] = max {  dp[i-1][j]    ,   dp[i-1][j-weight[i]]+value[i] }

 一维数组

dp[j] = max{ dp[j], dp[j-weight[i]]+value[i]   }

一维很难理解，今天看到一个别的的理解

dp[j]新 = max{dp[j]旧，dp[j-weight[i]]+value[i] }

（2）代码实现

二维数组方案

public static int maxValue(int[] weight, int[] value, int maxWeight) {
    int n = weight.length;
    if (n == 0) return 0;
    int[][] dp = new int[n + 1][maxWeight + 1];
    for (int i = 1; i <= n; i++) {
        for (int k = 1; k <= maxWeight; k++) {
            // 存放 i 号物品（前提是放得下这件物品）
            if(k>=weight[i-1]){
                dp[i][k] = Math.max(dp[i - 1][k], dp[i-1][k-weight[i-1]]+value[i-1]);
            }else{
                dp[i][k] = dp[i - 1][k];
            }
        }
    }
    return dp[n][maxWeight];
}

一维数组方案

需要注意，状态转移方程是从后往前推。跟完全背包不一样 

    public static int maxValue(int[] weight, int[] value, int W) {
        int n = weight.length;
        if (n == 0) return 0;
        int[] dp = new int[W + 1];
        for (int i = 0; i < n; i++) {
            //只要确保 k>=weight[i] 即可，而不是 k>=1，从而减少遍历的次数
            for (int k = W; k >= weight[i]; k--) {
                dp[k] = Math.max(dp[k - weight[i]] + value[i], dp[k]);
            }
        }
        return dp[W];
    }

完全背包

二维数组

dp[i][j] = max{    dp[i-1][j],      dp[i][j-weight[i]]+value[i]}

一维数组

dp[j] = max{ dp[j], dp[j-weight[i]]+value[i]   }

完全背包和0-1背包，状态转移方程很像，只有标红部分不同。

解决方案

回到322这个题目，这题是完全背包问题

dp[i][j]表示前N种硬币，总金额是j时，最少的数据量。

dp[i][j]=min{dp[i-1][j],   dp[i][j-coin[i]]+1 }

初始化dp[0][0]=0,默认金币个数是0时，都是不可实现方案，初始化dp[0][i]等于某个很大的值

public static int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        int[][] dp = new int[coins.length + 1][amount + 1];
        int initValue = Integer.MAX_VALUE / 2;
        dp[0][0] = 0;
        for (int i = 1; i < amount + 1; i++) {
            dp[0][i] = initValue;
        }
        for (int i = 1; i < coins.length + 1; i++) {
            for (int j = 0; j <= amount; j++) {
                if (j >= coins[i - 1]) {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[coins.length][amount] == initValue ? -1 : dp[coins.length][amount];
    }

一维实现方案

public static int coinChange1(int[] coins, int amount) {
    if (amount == 0) {
        return 0;
    }
    int[] dp = new int[amount + 1];
    int initValue = Integer.MAX_VALUE / 2;
    Arrays.fill(dp, initValue);
    dp[0] = 0;
    for (int i = 1; i < coins.length + 1; i++) {
        for (int j = coins[i - 1]; j < amount+1; j++) {
            dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
        }
    }
    return dp[amount] == initValue ? -1 : dp[amount];
}