动态规划算法专题（八）：01 背包问题
目录
1. 01背包【模版】
1.1 算法原理
- 状态表示:
1) dp[i][j]：从前i个物品中挑选，总体积 不超过j 的所有挑法中，最大价值
2) dp[i][j]：从前i个物品中挑选，总体积 恰好等于j 的所有挑法中，最大价值
- 状态转移方程:
1) 第一问
不选物品i --> dp[i-1][j]
选物品i --> j-v(i) >= 0 --> dp[i-1][j-v(i)]+w(i)
dp[i][j]=max(dp[i-1][j], dp[i-1][j-v(i)]+w(i))
2) 第二问
(在使用前面的状态时，都应该判断一下前面的状态是否能凑到, 若不能凑到则dp[i][j] == -1)
不选物品i --> dp[i-1][j]
选物品i --> j-v(i) >= 0 && dp[i-1][j-v(i)] != -1 --> dp[i-1][j-v(i)]+w(i)
(必须在前面选时，凑出j-v(i)的体积)
- 初始化：
1) 第一问
没有物品 --> 第一行初始化为0； 容量为0 --> 第一列初始化为0
2) 第二问
dp[0][0] = 0;// 没有物品, 但是书包的容量也为0
dp[0][1~V] = -1;// 没有物品, 凑不满书包的容量
dp[1~n][0] = 0;
- 建表顺序：
从上往下每一行，
从左往右每一列
- 返回值：
dp[n][V]
1.2 算法代码
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt(), V = in.nextInt();
int[] arrV = new int[n + 1];
int[] arrW = new int[n + 1];
int x = 1;
while (x <= n) { // 注意 while 处理多个 case
arrV[x] = in.nextInt();
arrW[x] = in.nextInt();
x++;
}
int[][] dp1 = new int[n + 1][V + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= V; j++) {
dp1[i][j] = dp1[i - 1][j];
if(j - arrV[i] >= 0)
dp1[i][j] = Math.max(dp1[i][j], dp1[i - 1][j - arrV[i]] + arrW[i]);
}
}
int[][] dp2 = new int[n + 1][V + 1];
Arrays.fill(dp2[0], -1);
dp2[0][0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= V; j++) {
dp2[i][j] = dp2[i - 1][j];
if(j - arrV[i] >= 0 && dp2[i - 1][j - arrV[i]] != -1)
dp2[i][j] = Math.max(dp2[i][j], dp2[i - 1][j - arrV[i]] + arrW[i]);
}
}
System.out.println(dp1[n][V]);
if(dp2[n][V] != -1) System.out.println(dp2[n][V]);
else System.out.println(0);
}
}1.3 空间优化版本
dp表中的元素, 依赖于其上一行中的数据, 所以我们可以进行空间优化, 将二维的dp表优化成一维的dp表.
注意: 由于每个元素依赖的是其上一行同一列以及上一行左列的值, 所以优化时应从左往右建表.
并且, 在优化空间时, 也会对时间进行常数级别的优化.
1.4 空间优化版本代码
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt(), V = in.nextInt();
int[] arrV = new int[n + 1];
int[] arrW = new int[n + 1];
int x = 1;
while (x <= n) { // 注意 while 处理多个 case
arrV[x] = in.nextInt();
arrW[x] = in.nextInt();
x++;
}
int[] dp1 = new int[V + 1];
for(int i = 1; i <= n; i++) {
for(int j = V; j >= arrV[i]; j--) {
dp1[j] = dp1[j];
dp1[j] = Math.max(dp1[j], dp1[j - arrV[i]] + arrW[i]);
}
}
int[] dp2 = new int[V + 1];
// 初始化
Arrays.fill(dp2, -1);
dp2[0] = 0;
for(int i = 1; i <= n; i++) {
for(int j = V; j >= arrV[i]; j--) {
dp2[j] = dp2[j];
if(dp2[j - arrV[i]] != -1)
dp2[j] = Math.max(dp2[j], dp2[j - arrV[i]] + arrW[i]);
}
}
System.out.println(dp1[V]);
System.out.println(dp2[V] == -1 ? 0 : dp2[V]);
}
}2. 分割等和子集
2.1 算法原理
- 问题转化:
将数组分割两个等和的子集 --> 数组是否存在和为 sum / 2 的子集
- 状态表示:
dp[i][j]: 从前 i 个数中选, 能否凑成 j 这个数
- 状态转移方程:
选 i --> if(j - nums[i] >= 0) --> dp[i - 1][j - nums[i]]
不选 i --> dp[i - 1][j]
dp[i][j] = dp[i - 1][j - nums[i]] || dp[i - 1][j]
- 初始化:
多开辟一行, 多开辟一列.
1. 下标映射
2. 里面的值要保证后续的填表是正确的
- 建表顺序:
从上往下
- 返回值:
dp[n][sum / 2]
2.2 算法代码
class Solution {
public boolean canPartition(int[] nums) {
// 数组是否存在和为 sum / 2 的子集
int n = nums.length;
int sum = 0;
for(int x : nums) sum += x;
if(sum % 2 != 0) return false;
boolean[][] dp = new boolean[n + 1][sum / 2 + 1];
// 初始化
for(int i = 0; i <= n; i++) dp[i][0] = true;
// 填表
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= sum / 2; j++) {
dp[i][j] = dp[i - 1][j];
if(j - nums[i - 1] >= 0) dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][sum / 2];
}
/**
* 空间优化
* @param nums
* @return
*/
public boolean canPartition1(int[] nums) {
// 空间优化版本
// 数组是否存在和为 sum / 2 的子集
int n = nums.length;
int sum = 0;
for(int x : nums) sum += x;
if(sum % 2 != 0) return false;
boolean[] dp = new boolean[sum / 2 + 1];
// 初始化
dp[0] = true;
// 填表
for(int i = 1; i <= n; i++) {
for(int j = sum / 2; j >= nums[i - 1]; j--) {
dp[j] = dp[j] || dp[j - nums[i - 1]];
}
}
return dp[sum / 2];
}
}3. 目标和
3.1 算法原理
- 问题转化:
从数组中选一些数, 使这些数总和为 a , 一共有多少种选法
- 状态表示dp[i][j]:
从数组前 i 个位置中选, 使得总和为 j , 一共有多少种选法
- 状态转移方程:
选 i --> j - nums[i] >= 0 --> dp[i- 1][j - nums[i]]
不选 i --> dp[i - 1][j]
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j]
- 建表顺序:
从上往下
- 返回值:
dp[n][a]
3.2 算法代码
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int n = nums.length;
int sum = 0;
for(int x : nums) sum += x;
int aim = (sum + target) / 2;
if(aim < 0 || (sum + target) % 2 == 1) return 0;
int[][] dp = new int[n + 1][aim + 1];
dp[0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= aim; j++) {
dp[i][j] = dp[i - 1][j];
if(j - nums[i - 1] >= 0) dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
return dp[n][aim];
}
/**
* 空间优化
* @param nums
* @param target
* @return
*/
public int findTargetSumWays1(int[] nums, int target) {
int n = nums.length;
int sum = 0;
for(int x : nums) sum += x;
int aim = (sum + target) / 2;
if(aim < 0 || (sum + target) % 2 == 1) return 0;
int[] dp = new int[aim + 1];
dp[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = aim; j >= nums[i - 1]; j--) {
dp[j] += dp[j - nums[i - 1]];
}
}
return dp[aim];
}
}4. 最后一块石头的重量 II
4.1 算法原理
- 问题转化:
从数组中选出一些数, 使和最接近 sum / 2
- 状态表示dp[i][j]:
从数组的前 i 个位置中选, 总和不超过 j, 此时的最大和
- 状态转移方程:
选 i --> j - nums[i] >= 0 --> dp[i- 1][j - nums[i]] + nums[i]
不选 i --> dp[i - 1][j]
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - nums[i]] + nums[i])
- 建表顺序:
从上往下
- 返回值:
sum - dp[n][sum / 2] * 2
4.2 算法代码
class Solution {
public int lastStoneWeightII(int[] stones) {
int n = stones.length;
int sum = 0;
for(int x : stones) sum += x;
int[][] dp = new int[n + 1][sum / 2 + 1];
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= sum / 2; j++) {
dp[i][j] = dp[i - 1][j];
if(j - stones[i - 1] >= 0)
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
int ret = sum - dp[n][sum / 2];
return Math.abs(ret - dp[n][sum / 2]);
}
/**
* 空间优化
* @param stones
* @return
*/
public int lastStoneWeightII1(int[] stones) {
int n = stones.length;
int sum = 0;
for(int x : stones) sum += x;
int[] dp = new int[sum / 2 + 1];
for(int i = 1; i <= n; i++) {
for(int j = sum / 2; j >= stones[i - 1]; j--) {
dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
}
}
int ret = sum - dp[sum / 2];
return Math.abs(ret - dp[sum / 2]);
}
}END
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
42
0- 0
已为社区贡献9条内容
所有评论(0)