无锡八匹马网站建设,thinkphp网站开发服务器,桌面网站怎么做,什么网站可以做论文目录 题目
背包状态转移方程
0-1背包
完全背包
解决方案 题目
给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金…目录 题目
背包状态转移方程
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(kweight[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) {//只要确保 kweight[i] 即可而不是 k1从而减少遍历的次数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 amount1; j) {dp[j] Math.min(dp[j], dp[j - coins[i - 1]] 1);}}return dp[amount] initValue ? -1 : dp[amount];
}
