网站后台管理系统素材网站建设报价东莞

什么是01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

01背包的模板

二维dp数组

dp数组的含义

dp[i][j]含义下标为【0-i】之间的物品任取放进容量为j的背包里的最大价值

递推公式

dp[i][j]的值取决于放不放物品i
如果不放物品i：dp[i][j]为dp[i-1][j]
如果放物品i：dp[i-1][j-w[i]] 保证可以放入物品i（0-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 sum=0;for(int i=0;i<nums.length;i++){sum+=nums[i];}if(sum%2!=0){return false;}int capation = sum/2;int[] dp = new int[capation+1];for(int i=0;i<nums.length;i++) {for(int j=capation;j>=nums[i];j--){dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);}}if(dp[capation]==capation){return true;}else{return false;}}
}