0-1背包问题 二维
动规五部曲
1、确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。（取物品时可以是取0-i的任意一个，或者是他们的组合）
2、确定递推公式
- 不放物品i：背包容量为j，里面不放物品i的最大价值是dp[i - 1][j]。
- 放物品i：背包空出物品i的容量后，背包容量为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[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0。
-
状态转移方程i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。当 j < weight[0]的时候，dp[0][j] = 0，当j >= weight[0]时，dp[0][j] =value[0]。
4、确定遍历顺序
先遍历物品，然后遍历背包重量。
5、举例推导dp数组
代码如下：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner =new Scanner(System.in);
int m=scanner.nextInt();
int n=scanner.nextInt();
int[] weight=new int[m];
int[] value=new int[m];
for(int i=0;i<m;i++){
weight[i]=scanner.nextInt();
}
for(int i=0;i<m;i++){
value[i]=scanner.nextInt();
}
int[][] dp=new int[m][n+1];
//背包为0时，价值为0
for(int i=0;i<m;i++){
dp[i][0]=0;
}
for(int j=0;j<=n;j++){
if(j<weight[0]) dp[0][j]=0;
else dp[0][j]=value[0];
}
for(int i=1;i<m;i++){
for(int j=1;j<=n;j++){
if(j<weight[i]) dp[i][j]=dp[i-1][j];
else dp[i][j]=Math.max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j]);
}
}
System.out.println(dp[m-1][n]);
}
}
0-1背包问题 一维
前言：将二维dp降为一维dp。使用二维数组时，递推公式为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数组的递推公式
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
理解：dp[j]为容量为j的背包所背的最大价值。dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示 容量为 [j - 物品i重量] 的背包 加上 物品i的价值。此时dp[j]有两个选择，一个是取自己dp[j] ，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i。
3、一维dp数组如何初始化
dp[0]=0，由于递归公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
dp数组在推导的时候一定是取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。
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]);
}
}
5、举例推导dp数组
代码如下：
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner =new Scanner(System.in);
int m=scanner.nextInt();
int n=scanner.nextInt();
int[] weight=new int[m];
int[] value=new int[m];
for(int i=0;i<m;i++){
weight[i]=scanner.nextInt();
}
for(int i=0;i<m;i++){
value[i]=scanner.nextInt();
}
int[] dp=new int[n+1];
//全部初始化为0
for(int i=0;i<=n;i++){
dp[i]=0;
}
for(int i=0;i<m;i++){
for(int j=n;j>=0;j--){
if(j>=weight[i]) dp[j]=Math.max(dp[j-weight[i]]+value[i],dp[j]);
}
}
System.out.println(dp[n]);
}
}
416. 分割等和子集
思路：整体思路是判断元素和能否平分，将sum / 2作为背包的总体积，找到一个即表明存在，return即可。
首先，确定了如下四点，才能把01背包问题套到本题上来:
- 背包的体积为sum / 2
- 背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
- 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
- 背包中每一个元素是不可重复放入。
可以直接套背包问题的动规五部曲，这里就不赘述了。
代码如下：
class Solution {
public boolean canPartition(int[] nums) {
if(nums==null || nums.length==0) return false;
int sum=0;
for(int num:nums) sum+=num;
if(sum%2==1) return false;
int target=sum/2;
int[] dp=new int[target+1];
for(int i=0;i<nums.length;i++){
for(int j=target;j>=nums[i];j--){
dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
}
if(dp[target]==target) return true;
}
return dp[target]==target;
}
}