当前位置：首页 > news >正文

leetcode322零钱兑换（背包问题）

news 来源：原创 2024/9/29 3:28:27

题目

背包状态转移方程

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];
}