扬州网站建设icp备,网站开发项目视频,云霄城乡建设局网站,德州公司做网站什么是01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]#xff0c;得到的价值是value[i] 。每件物品只能用一次#xff0c;求解将哪些物品装入背包里物品价值总和最大。
01背包的模板
二维dp数组
dp数组的含义
dp[i][j]含义下标为【0-i】之间…什么是01背包
有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
01背包的模板
二维dp数组
dp数组的含义
dp[i][j]含义下标为【0-i】之间的物品任取放进容量为j的背包里的最大价值
递推公式
dp[i][j]的值取决于放不放物品i 如果不放物品idp[i][j]为dp[i-1][j] 如果放物品idp[i-1][j-w[i]] 保证可以放入物品i0-i-1的物品不放入i时的最大价值 dp[i][j] 为dp[i-1][j-w[i]]v[i] dp[i][j] 求两者最大值 递推公式 dp[i][j]max(dp[i-1][j],dp[i-1][j-w[i]]w[i])
初始化
第一行和第一列均初始化
for (int j 0 ; j weight[0]; j) { dp[0][j] 0;
}
// 正序遍历
for (int j weight[0]; j bagweight; j) {dp[0][j] value[0];
}遍历
有两个遍历维度 物品和背包 两个遍历顺序 正序遍历和倒序遍历 先遍历 物品还是先遍历背包重量呢 其实都可以 但是先遍历物品更好理解。
for(int i 1; i weight.size(); i) { // 遍历物品for(int j 0; j bagweight; j) { // 遍历背包容量//如果整体的背包容量小于物品重量 dp[i][j] dp[i - 1][j];//前i-1个物品能放下的最大价值就是当前情况的最大价值if (j weight[i]) dp[i][j] dp[i - 1][j];else dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]);}
}一维dp数组
在使用二维数组的时候递推公式dp[i][j] max(dp[i - 1][j], dp[i - 1][j - weight[i]] value[i]); 我们发现可以把dp[i]的值覆盖到dp[i-1]上 这样可以实现一维数组 如果把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]一维数组也可以理解是一个滚动数组
一维dp数组的动规五部曲分析
dp数组的含义 dp[j] 容量为j的背包的最大价值 递推公式 dp[j] max(dp[j],dp[j-w[j]]v[j]) dp[j] 表示不放物品j即拷贝上一层 初始化 初始化 dp[0]0; 非0下标初始化为0 遍历顺序
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]);}
}为什么是倒序遍历 正序遍历的话 会依托前面的dp[j] 正向遍历前面的dp[j]会被覆盖 之后再使用时 不是上一层的dp[j] 而是当前层新更新的dp[j] 这个dp[j]可能已经加入过物品i 这就导致i被重复添加 倒序遍历时 前面的dp[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. 分割等和子集
题目链接416. 分割等和子集 解题思路数组的数字是物品其重量和价值都是该数字。背包的容量是总和的一半。如果物品价值可以达到容量 则说明可以被分割 代码如下
class Solution {public boolean canPartition(int[] nums) {//求背包容量int sum0;for(int i0;inums.length;i){sumnums[i];}if(sum%2!0){return false;}int capation sum/2;int[] dp new int[capation1];for(int i0;inums.length;i) {for(int jcapation;jnums[i];j--){dp[j]Math.max(dp[j],dp[j-nums[i]]nums[i]);}}if(dp[capation]capation){return true;}else{return false;}}
}
