背包问题总览
如下图，备战面试，重点是 01 背包，完全背包，多重背包了解即可。
01 背包问题（二维数组）
- 步骤一：确认 dp 数组及下标的含义
- dp[i][j]表示从下标为[0,i]的物品中，选取任意的物品并放入容量为 j 的背包的价值总和。
- 步骤二：确认递推公式
- dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]);
- 步骤三：初始化 dp 数组
- 步骤四：确定遍历顺序
- 两层 for 循环，先遍历物品或者背包重量都可以，正向遍历
- 步骤五：举例推导
01 背包问题（一维数组）
- 步骤一：确认 dp 数组及下标的含义
- dp[j]表示容量为 j 的背包所背物品的最大价值。
- 步骤二：确认递推公式
- dp[j] = max(dp[j], dp[j-weight[i]] + value[i])
- 步骤三：初始化 dp 数组
- 步骤四：确定遍历顺序
- 先遍历物品再遍历背包，不可以颠倒顺序
- 步骤五：举例推导
416. 分割等和子集
此题需要特殊处理一下异常情况，如某个数超过总和一半。
二维数组解法：
package jjn.carl.dp; /** * @author Jiang Jining * @since 2023-08-13 9:40 */ public class LeetCode416 { public boolean canPartition(int[] nums) { int sum = 0; int max = nums[0]; for (int num : nums) { sum += num; max = Math.max(max, num); } if (sum % 2 == 1) { return false; } int target = sum / 2; if (max > target) { return false; } boolean[][] dp = new boolean[nums.length][target + 1]; for (int i = 0; i < nums.length; i++) { dp[i][0] = true; } dp[0][nums[0]] = true; for (int i = 1; i < nums.length; i++) { int num = nums[i]; for (int j = 1; j <= target; j++) { if (j >= num) { dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]; } else { dp[i][j] = dp[i - 1][j]; } } } return dp[nums.length - 1][target]; } }
一维数组解法：
package jjn.carl.dp; /** * @author Jiang Jining * @since 2023-08-13 15:21 */ public class LeetCode416_2 { public boolean canPartition(int[] nums) { int sum = 0; int maxNum = nums[0]; for (int num : nums) { sum += num; maxNum = Math.max(maxNum, num); } if (sum % 2 == 1) { return false; } int target = sum / 2; if (maxNum > target) { return false; } boolean[] dp = new boolean[target + 1]; dp[0] = true; for (int i = 0; i < nums.length; i++) { for (int j = target; j >= nums[i]; j--) { dp[j] = dp[i - nums[j]] || dp[j]; } } return dp[target]; } }
