代码随想录算法训练营第四十一天 | 01背包问题（二维），01背包问题（一维），416.分割等和子集
01背包问题（二维）及背包问题理论基础
背包问题理论讲解及题目讲解：代码随想录
重点：
理解01背包二维数组的dp数组的含义，递推公式，初始化及遍历顺序
思路：
- dp数组的含义
// 从物品[0-i]里任意取几个，放进容量为j的背包，最大是多少 int[][] dp = new int[n][bagweight + 1];
- 递推公式
// 当前背包容量放不进物品i if (j < weight[i]) { dp[i][j] = dp[i - 1][j]; // 当前背包能放进物品i，则递推公式有两种情况，取不放物品i和放物品i的最大值 } else { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); }
- dp数组初始化
// 背包容量为0时，价值最大为0 for (int i = 0; i < n; i++) { dp[i][0] = 0; } // 只能物品0可以选择是否放入 for (int j = 0; j <= bagweight; j++) { // 背包容量比物品0小 if (j < weight[0]) { dp[0][j] = 0; // 背包容量比物品0大 } else { dp[0][j] = value[0]; } }
- 遍历顺序
// 先遍历物品再遍历背包 for (int i = 1; i < n; i++) for (int j = 0; j <= bagweight; j++)
- 模拟dp数组
public static void main(String[] args) {
// 读取输入
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[n];
int[] value = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
value[i] = scanner.nextInt();
}
// 从物品[0-i]里任意取几个，放进容量为j的背包，最大是多少
int[][] dp = new int[n][bagweight + 1];
// 背包容量为0时，价值最大为0
for (int i = 0; i < n; i++) {
dp[i][0] = 0;
}
// 只能物品0可以选择是否放入
for (int j = 0; j <= bagweight; j++) {
// 背包容量比物品0小
if (j < weight[0]) {
dp[0][j] = 0;
// 背包容量比物品0大
} else {
dp[0][j] = value[0];
}
}
// 先遍历物品再遍历背包
for (int i = 1; i < n; i++) {
for (int j = 0; j <= bagweight; j++) {
// 当前背包容量放不进物品i
if (j < weight[i]) {
dp[i][j] = dp[i - 1][j];
// 当前背包能放进物品i，则递推公式有两种情况，取不放物品i和放物品i的最大值
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
}
}
}
System.out.println(dp[n - 1][bagweight]);
}
01背包问题（一维）及背包问题理论基础
题目讲解：代码随想录
重点：
理解01背包一维数组的递推公式，遍历顺序
思路：
- dp数组的含义
// 容量为j的背包，所能背的最大价值 int[] dp = new int[bagweight + 1];
- 递推公式
// dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i， // dp[j - weight[i]] + value[i]，即放物品i，取最大的，毕竟是求最大价值 if (j < weight[i]) { dp[j] = dp[j]; } else { dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); }
- dp数组初始化
// 这样才能让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了 for (int i = 0; i < dp.length; i++) { dp[i] = 0; }
- 遍历顺序
// 先正序遍历物品，再倒序遍历背包 // 如果正序遍历背包，会重复放入物品，因为利用了新值 // 如果先遍历背包，再遍历物品，相当于背包里只放入了一个物品 for (int i = 0; i < n; i++) for (int j = bagweight; j >= 0; j--)
- 模拟dp数组
public static void main(String[] args) {
// 读取输入
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int bagweight = scanner.nextInt();
int[] weight = new int[n];
int[] value = new int[n];
for (int i = 0; i < n; i++) {
weight[i] = scanner.nextInt();
}
for (int i = 0; i < n; i++) {
value[i] = scanner.nextInt();
}
// dp[j]: 容量为j的背包，所能背的最大价值
int[] dp = new int[bagweight + 1];
// 让dp数组在递归公式的过程中取的最大的价值，而不是被初始值覆盖了
for (int i = 0; i < dp.length; i++) {
dp[i] = 0;
}
// 先正序遍历物品，再倒序遍历背包
// 如果正序遍历背包，会重复放入物品，因为利用了新值
// 如果先遍历背包，再遍历物品，相当于背包里只放入了一个物品
for (int i = 0; i < n; i++) {
for (int j = bagweight; j >= 0; j--) {
// 放不进物品i
if (j < weight[i]) {
dp[j] = dp[j];
// 放的进物品i，则有放入物品i价值最大和不放入物品i价值最大
} else {
dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}
// 其实可以简化，如果都放不进物品i了，循环都没必要到0，只到weight[i]即可
// 因为都不用更新滚动数组的值，滚动数组的值就是二维数组上一行的值
}
}
System.out.println(dp[bagweight]);
}
416. 分割等和子集
题目讲解：代码随想录
重点：
把这道题转化成01背包问题
思路：
- dp数组的含义
// 容量为j的背包能放得最大数值和 int[] dp = new int[target + 1];
- 递推公式
// 放入数字i和不放入数字i dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
- dp数组的初始化
// 因为递推公式取的是max dp[j] = 0
- 遍历顺序
// 先正序遍历nums，再反序遍历背包容量 for (int i = 0; i < nums.length; i++) for (int j = target; j >= nums[i]; j--)
- 模拟dp数组
public boolean canPartition(int[] nums) {
/*
分析题目：
1. 背包容量为sum/2
2. 每个物品的价值和重量都是他的数值
3. dp[sum/2]==sum/2则返回true，因为等和的数值的背包能够被装满
*/
// 计算和及检查存在等和子集的可能
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
// 背包容量就为等和子集的和
int target = sum / 2;
// dp[j] = 容量为j的背包能放得最大数值和
int[] dp = new int[target + 1];
// 先正序遍历数字，再倒序遍历背包大小
for (int i = 0; i < nums.length; i++) {
// j小于nums[i]没必要更新，因为都放不进去
for (int j = target; j >= nums[i]; j--) {
// 放入数字i和不放入数字i
dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
}
// 剪枝，看看当前取的前i个数字是否能够满足target
if (dp[target] == target) {
return true;
}
}
return dp[target] == target;
}