Javajava算法
动态规划解法：01 背包问题与分割等和子集
动态规划解决 01 背包问题，涵盖最大价值与恰好装满两种场景。通过状态定义推导一维滚动数组优化，将空间复杂度降至 O(V)。进一步应用该模型解决分割等和子集问题，提供完整的 Java 代码实现及详细步骤解析。
动态规划解决 01 背包问题，涵盖最大价值与恰好装满两种场景。通过状态定义推导一维滚动数组优化，将空间复杂度降至 O(V)。进一步应用该模型解决分割等和子集问题，提供完整的 Java 代码实现及详细步骤解析。
第一问： 求这个背包至多能装多大价值的物品？ 第二问： 若背包恰好装满，求至多能装多大价值的物品？
输入示例：
3 5
2 10
4 5
1 4
输出示例：
14
9
说明： 装第一个和第三个物品时总价值最大（14），但装第二个和第三个物品可以使得背包恰好装满且总价值最大（9）。
备注： 要求 O(nV) 的时间复杂度，O(V) 空间复杂度。
01 背包问题本质上是线性 DP 问题。使用二维定义：
dp[i][j] 表示在前 i 个位置中选择物品，物品总体积不超过 j 的所有选法中能选出来的最大价值。
根据最后一个位置是否选择来划分问题：
i 物品不选：dp[i][j] = dp[i-1][j]i 物品要选：需要保证剩余容量大于等于 0，即 j - v[i] >= 0，则 dp[i][j] = w[i] + dp[i-1][j - v[i]]
综合为：dp[i][j] = Math.max(dp[i-1][j], w[i] + dp[i-1][j - v[i]])选择物品是从下标 1 开始的，到 n 结束，那么 dp 表就需要多创建一行一列。
根据状态转移方程可知，要想得到 dp[i][j] 就得先知道 dp[i-1][j] 或者 dp[i-1][j-v[i]]，所以应该从上往下填写每一行，从左往右填写每一列。
打印 dp[n][V] 即可。
二维定义 dp[i][j] 表示在前 i 个位置中选择物品，物品总体积刚好为 j 的所有选法中能选出来的最大价值。
可能存在所有选法都不能恰好装满背包，我们规定此时 dp[i][j] = -1。
根据最后一个位置是否选择来划分问题：
i 物品不选：dp[i][j] = dp[i-1][j]i 物品要选：需要保证剩余容量大于等于 0，且前一步状态有效（不为 -1），即 j - v[i] >= 0 && dp[i-1][j - v[i]] != -1。
综合为：dp[i][j] = Math.max(dp[i-1][j], w[i] + dp[i-1][j - v[i]])dp[0][0] = 0，后面无论选不选，总价值都达不到 j，于是全都初始化为 -1。同上，从上往下，从左往右。
打印 dp[n][V] 即可。若是 -1 则输出 0。
利用滚动数组做空间上的优化，将二维数组压缩为一维数组。
i 维。j。import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = 1010;
int n = in.nextInt();
int V = in.nextInt();
int[] v = new int[N];
int[] w = new int[N];
for (int i = 1; i <= n; ++i) {
v[i] = in.nextInt();
w[i] = in.nextInt();
}
// 1. 解决第一个问题：求这个背包至多能装多大价值的物品
int[] dp1 = new int[N];
for (int i = 1; i <= n; ++i) {
for (int j = V; j >= v[i]; --j) {
dp1[j] = Math.max(dp1[j], w[i] + dp1[j - v[i]]);
}
}
System.out.println(dp1[V]);
// 2. 解决第二个问题：若背包恰好装满，求至多能装多大价值的物品
int[] dp2 = new int[N];
for (int i = 1; i <= V; ++i) {
dp2[i] = -1;
}
dp2[0] = 0;
for (int i = 1; i <= n; ++i) {
for (int j = V; j >= v[i]; --j) {
if (dp2[j - v[i]] != -1) {
dp2[j] = Math.max(dp2[j], w[i] + dp2[j - v[i]]);
}
}
}
System.out.println((dp2[V] == -1 ? 0 : dp2[V]));
}
}
给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1： 输入：nums = [1,5,11,5] 输出：true 解释：数组可以分割成 [1, 5, 5] 和 [11]。
示例 2： 输入：nums = [1,2,3,5] 输出：false 解释：数组不能分割成两个元素和相等的子集。
直接去判断两个子集的元素和是否相等会有点复杂，可以转化为只研究一个子集等于原数组元素和的一半，即在数组中选择一些数，这些数的和是否等于原数组元素和的一半。
dp[i][j] 表示在 nums 的前 i 个位置中选择一些数，所有选法中，是否存在一些数，使得这些数之和为 j。
根据最后一个位置 nums[i] 是否选择来划分情况：
nums[i] 不选：dp[i][j] = dp[i-1][j]nums[i] 要选：需要保证所选数之和不超过 j，即 j - nums[i] >= 0，则 dp[i][j] = dp[i-1][j - nums[i]]
综合为：dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]]dp 表多创建一行一列，需要处理两个问题：
i=0 意味着没有元素可选，怎么选最大值都只能是 false，所以 dp[0][0] = true，其余全部初始化为 false。j=0 意味着需要凑成和为 0，直接不选即可。故从 i=1 开始全部初始化为 true。根据状态转移方程可知，要想求得 dp[i][j] 就得先知道 dp[i-1][j] 和 dp[i-1][j-nums[i]]，所以可知填表顺序为：从上往下填写每一行，每一行从左往右填写。
返回 dp[nums.length][原数组元素和的一半]。
利用滚动数组做空间上的优化，将二维数组压缩为一维数组。
i 维。j。class Solution {
public boolean canPartition(int[] nums) {
int n = nums.length;
int sum = 0;
for (int x : nums) sum += x;
if (sum % 2 == 1) return false;
int aim = sum / 2;
boolean[] dp = new boolean[aim + 1];
dp[0] = true;
for (int i = 1; i <= n; ++i) {
for (int j = aim; j >= nums[i - 1]; --j) {
if (!dp[j]) {
dp[j] = dp[j - nums[i - 1]];
}
}
}
return dp[aim];
}
}
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online