当前位置：首页 > news >正文

代码随想录算法训练营第三十五天

news 2025/8/2 0:07:52

01背包问题二维

题目链接 01背包问题二维

题解

import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int M = sc.nextInt();int N = sc.nextInt();int[] space = new int[M];int[] value = new int[M];for(int i = 0;i<M;i++){space[i] = sc.nextInt();}for(int i = 0;i<M;i++){value[i] = sc.nextInt();}int[][] dp = new int[M+1][N+1];for(int i = 1;i<=M;i++){for(int j = 0;j<=N;j++){if(j < space[i-1]) dp[i][j] = dp[i-1][j];else dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-space[i-1]]+value[i-1]);}}System.out.println(dp[M][N]);}
}

解题思路

你提供的这段是 0-1 背包问题的另一种动态规划实现，与上一个版本相比，主要区别在于使用了二维数组来存储中间状态。

这段代码的逻辑解析：

同样先通过 Scanner 读取输入数据：
- M 表示物品数量
- N 表示背包的最大容量
- space 数组存储物品体积，value 数组存储物品价值
动态规划求解部分的差异：
- 使用二维数组 dp [i][j]，表示考虑前 i 个物品时，容量为 j 的背包能装下的最大价值
- 外层循环遍历物品数量 (i 从 1 到 M)
- 内层循环遍历背包容量 (j 从 0 到 N)
- 状态转移逻辑：
  - 如果当前物品体积大于背包容量 (j < space [i-1])，则不选该物品，dp [i][j] = dp [i-1][j]
  - 否则，在 "不选该物品" 和 "选该物品" 两种情况中取最大值
最终结果存储在 dp [M][N] 中，表示考虑所有 M 个物品时，容量为 N 的背包能获得的最大价值

与一维数组版本相比，这个二维数组版本的空间复杂度更高 (O (M×N))，但更容易理解，因为它清晰地展示了 "考虑前 i 个物品" 这个维度的状态变化，对于初学者来说更直观地体现了动态规划的递推过程。

01背包问题一维

题目链接 01背包问题一维

题解

import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int M = sc.nextInt();int N = sc.nextInt();int[] space = new int[M];int[] value = new int[M];for(int i = 0;i<M;i++){space[i] = sc.nextInt();}for(int i = 0;i<M;i++){value[i] = sc.nextInt();}int[] dp = new int[N+1];for(int i = 1;i<=M;i++){for(int j = N;j>=space[i-1];j--){dp[j] = Math.max(dp[j],dp[j-space[i-1]] + value[i-1]);}}System.out.println(dp[N]);}
}

解题思路

你提供的这段代码实现了经典的 0-1 背包问题的动态规划解法，功能是在给定背包容量限制下，选择物品使得总价值最大。

代码的主要逻辑解析：

首先通过 Scanner 读取输入数据：
- M 表示物品数量
- N 表示背包的最大容量
- 然后分别读取 M 个物品的体积 (space 数组) 和价值 (value 数组)
使用动态规划求解：
- 创建 dp 数组，dp [j] 表示容量为 j 的背包能装下的最大价值
- 采用逆序遍历的方式 (从 N 到 space [i-1])，避免同一个物品被多次选择
- 状态转移方程：dp [j] = Math.max (dp [j], dp [j-space [i-1]] + value [i-1])
  表示对于当前物品，选择装或不装，取两种情况的最大值
最后输出 dp [N]，即容量为 N 的背包所能装下的最大价值

这段代码是 0-1 背包问题的标准实现，时间复杂度为 O (M×N)，空间复杂度为 O (N)，逻辑清晰且高效。

LeetCode.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 == 1) return false;int target = sum / 2;int[] dp = new int[target+1];for(int i = 1;i<=nums.length;i++){for(int j = target;j >= nums[i-1];j--){dp[j] = Math.max(dp[j],dp[j-nums[i-1]] + nums[i-1]);}}return dp[target] == target;}
}

题解二

class Solution {public boolean canPartition(int[] nums) {int sum = 0;for (int num : nums) {sum += num;}// 如果总和是奇数，不可能分割成两个相等的子集if (sum % 2 == 1) {return false;}int target = sum / 2;int n = nums.length;// 二维int类型DP数组：dp[i][j]表示前i个元素能组成的不超过j的最大和int[][] dp = new int[n + 1][target + 1];// 填充DP数组for (int i = 1; i <= n; i++) {for (int j = 0; j <= target; j++) {// 不选第i个元素（即nums[i-1]）dp[i][j] = dp[i-1][j];// 选第i个元素（如果当前元素值不超过j）if (j >= nums[i-1]) {dp[i][j] = Math.max(dp[i][j], dp[i-1][j - nums[i-1]] + nums[i-1]);}}}// 如果最大和等于目标值，说明可以分割return dp[n][target] == target;}
}

解题思路

这两种解法都基于动态规划思想，核心是将 "分割等和子集" 问题转化为 0-1 背包问题来解决，具体解题思路如下：

问题转化

要将数组分割成两个等和子集，等价于判断是否存在一个子集，其元素之和等于数组总元素和的一半（记为target）
这可以转化为 0-1 背包问题：从数组中选择元素，使它们的和恰好等于target（背包容量为target，每个元素的重量和价值都是其自身值）

核心思路

计算总和与判断可行性：
- 先计算数组所有元素的总和sum
- 若sum为奇数，不可能分割成两个等和子集，直接返回false
- 若sum为偶数，计算目标值target = sum / 2
动态规划求解：
- 两种解法都通过 DP 数组记录 "能否组成特定和" 的状态
- 题解一使用一维数组dp[j]，表示能组成的不超过j的最大和
- 题解二使用二维数组dp[i][j]，表示前i个元素能组成的不超过j的最大和
- 状态转移逻辑：对每个元素，判断 "选" 或 "不选" 该元素，取两种情况的最大值
结果判断：
- 若最终 DP 数组中对应target位置的值等于target，说明存在这样的子集，返回true
- 否则返回false