好的网站建设方案,免费淘宝关键词工具,网站定制站,爱站官网本文参考#xff1a;代码随想录代码随想录
动态规划#xff1a;01背包理论基础
01背包问题#xff1a;有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物…本文参考代码随想录代码随想录
动态规划01背包理论基础
01背包问题有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
1. 确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取放进容量为j的背包价值总和最大是多少
2. 确定递推公式
那么可以有两个方向推出来dp[i][j]
不放物品i由dp[i - 1][j]推出即背包容量为j里面不放物品i的最大价值此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时物品i无法放进背包中所以背包内的价值依然和前面相同。)放物品i由dp[i - 1][j - weight[i]]推出dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值那么dp[i - 1][j - weight[i]] value[i] 物品i的价值就是背包放物品i得到的最大价值
所以递归公式 dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
3. dp数组如何初始化
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
首先从dp[i][j]的定义出发如果背包容量j为0的话即dp[i][0]无论是选取哪些物品背包价值总和一定为0。 j weight[0]的时候dp[0][j] 应该是 0因为背包容量比编号0的物品重量还小。
当j weight[0]时dp[0][j] 应该是value[0]因为背包容量放足够放编号0物品。
4. 确定遍历顺序
按照递推公式可得需要用表格上方和左上方的数据所以只要从后往前遍历先递归物品/先递归背包重量都是可以的
先递归物品更好理解
public class BagProblem {public static void main(String[] args) {int[] weight {1,3,4};int[] value {15,20,30};int bagSize 4;testWeightBagProblem(weight,value,bagSize);}/*** 动态规划获得结果* param weight 物品的重量* param value 物品的价值* param bagSize 背包的容量*/public static void testWeightBagProblem(int[] weight, int[] value, int bagSize){// 创建dp数组int goods weight.length; // 获取物品的数量int[][] dp new int[goods][bagSize 1];// 初始化dp数组// 创建数组后其中默认的值就是0for (int j weight[0]; j bagSize; j) {dp[0][j] value[0];}// 填充dp数组for (int i 1; i weight.length; i) {for (int j 1; j bagSize; j) {if (j weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候是不放物品i的* 那么前i-1个物品能放下的最大价值就是当前情况的最大价值*/dp[i][j] dp[i-1][j];} else {/*** 当前背包的容量可以放下物品i* 那么此时分两种情况* 1、不放物品i* 2、放物品i* 比较这两种情况下哪种背包中物品的最大价值最大*/dp[i][j] Math.max(dp[i-1][j] , dp[i-1][j-weight[i]] value[i]);}}}// 打印dp数组for (int i 0; i goods; i) {for (int j 0; j bagSize; j) {System.out.print(dp[i][j] \t);}System.out.println(\n);}}
}动态规划01背包理论基础滚动数组
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);
其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上表达式完全可以是dp[i][j] max(dp[i][j], dp[i][j - weight[i]] value[i]);
与其把dp[i - 1]这一层拷贝到dp[i]上不如只用一个一维数组了只用dp[j]一维数组也可以理解是一个滚动数组。
1. 确定dp数组的定义
在一维dp数组中dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]。
2. 一维dp数组的递推公式
二维数组减少一维把[i-1]那排的数据就储存在dp[i]上
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
3. 一维dp数组如何初始化
关于初始化一定要和dp数组的定义吻合否则到递推公式的时候就会越来越乱。
dp[j]表示容量为j的背包所背的物品价值可以最大为dp[j]那么dp[0]就应该是0因为背包容量为0所背的物品的最大价值就是0。
根据
dp[j] max(dp[j], dp[j - weight[i]] value[i]);
dp数组在推导的时候一定是取价值最大的数如果题目给的价值都是正整数那么非0下标都初始化为0就可以了范围内的最小值。
这样才能让dp数组在递归公式的过程中取的最大的价值而不是被初始值覆盖了。
4. 一维dp数组遍历顺序
for(int i 0; i weight.size(); i) { // 遍历物品for(int j bagWeight; j weight[i]; j--) { // 遍历背包容量dp[j] max(dp[j], dp[j - weight[i]] value[i]);}
}
1倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
举一个例子物品0的重量weight[0] 1价值value[0] 15
如果正序遍历
dp[1] dp[1 - weight[0]] value[0] 15
dp[2] dp[2 - weight[0]] value[0] 30 此时的dp[1]已经不是上一层的值了由于第一步已经被更新过是这一层的值了而压缩数组的思路就是把来利用上一次计算的值滚动更新数组所以计算的时候应该应用上次计算的值
此时dp[2]就已经是30了意味着物品0被放入了两次所以不能正序遍历。
倒序就是先算dp[2]
dp[2] dp[2 - weight[0]] value[0] 15 dp数组已经都初始化为0
dp[1] dp[1 - weight[0]] value[0] 15
所以从后往前循环每次取得状态不会和之前取得状态重合这样每种物品就只取一次了。
并且之后的计算不会用到新计算的数据
倒序遍历的原因是本质上还是一个对二维数组的遍历并且右下角的值依赖上一层左上角的值因此需要保证左边的值仍然是上一层的从右向左覆盖。
2不可以改变两个嵌套循环的顺序
不可以
因为一维dp的写法背包容量一定是要倒序遍历原因上面已经讲了如果遍历背包容量放在上一层那么每个dp[j]就只会放入一个物品此时dp[x] xj全部都是初始化0所以最终dp[j]其实就是价值最大的那个物品只放入了一个然后j--,后序逻辑相同即背包里只放入了一个物品。 public static void main(String[] args) {int[] weight {1, 3, 4};int[] value {15, 20, 30};int bagWight 4;testWeightBagProblem(weight, value, bagWight);}public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){int wLen weight.length;//定义dp数组dp[j]表示背包容量为j时能获得的最大价值int[] dp new int[bagWeight 1];//遍历顺序先遍历物品再遍历背包容量for (int i 0; i wLen; i){for (int j bagWeight; j weight[i]; j--){dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]);}}//打印dp数组for (int j 0; j bagWeight; j){System.out.print(dp[j] );}} 416. 分割等和子集
要明确本题中我们要使用的是01背包因为元素我们只能用一次。
首先本题要求集合里能否出现总和为 sum / 2 的子集。
只有确定了如下四点才能把01背包问题套到本题上来。
背包的体积(重量极限)为sum / 2背包要放入的商品集合里的元素重量为 元素的数值价值也为元素的数值背包如果正好装满说明找到了总和为 sum / 2 的子集。因为是找最大值所以尽可能的能够利用所有的重量如果无法找到相等的就说明没办法找到子集背包中每一个元素是不可重复放入。 转换为一个01背包问题背包大小为sum/2找到dp[sum/2]sum/2
1 如果sum为奇数可以直接剪枝返回false
2 每次检查jp[j] ,剪枝一下每一次完成內層的for-loop立即檢查是否dp[target] target,只要找到就说明可以完成不需要循环下去了
class Solution {public boolean canPartition(int[] nums) {if(nums null || nums.length 0) return false;int n nums.length;int sum 0;for(int num : nums) {sum num;}//总和为奇数不能平分if(sum % 2 ! 0) return false;int target sum / 2;int[] dp new int[target 1];for(int i 0; i n; i) {for(int j target; j nums[i]; j--) {//物品 i 的重量是 nums[i]其价值也是 nums[i]dp[j] Math.max(dp[j], dp[j - nums[i]] nums[i]);}//剪枝一下每一次完成內層的for-loop立即檢查是否dp[target] target優化時間複雜度26ms - 20msif(dp[target] target)return true;}return dp[target] target;}
}
