背包问题

背包问题（Knapsack problem）是一种组合优化的 NP 完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中，背包的空间有限，但我们需要最大化背包内所装物品的价值。背包问题通常出现在资源分配中，决策者必须分别从一组不可分割的项目或任务中进行选择，而这些项目又有时间或预算的限制。https://zh.m.wikipedia.org/zh/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98

参考：
Y总《背包九讲》
代码随想录
书：《图解算法》Aditya Bhargava

1. 0-1 背包
2. 完全背包问题

1. 0-1 背包

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $C_i$，价值是 $W_i$，
求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

暴力法：
列举每种情况，时间复杂为 $O(2^N)$。

动态规划1：
dp[i][j] 表示 [0, i] 物品任意取放入到容量为 j 的背包里的最大价值。

dp 数组初始化：dp[i][0] 均为 0，dp[0][0~物品 0 的体积-1] 均为 0。
任取 [ 0 , i ] 物品 , 体积为 j 时的最大价值 = m a x { 任取物品 [ 0 , i − 1 ] , 且体积为 j 最大价值 任取物品 [ 0 , i − 1 ] , 体积为 ( j − 物品 i 的体积 ) 时的最大价值 + 物品 i 的价值 任取[0,i]物品,体积为 j 时的最大价值= max \left\{

\right. 任取[0,i]物品,体积为j时的最大价值=max{​任取物品[0,i−1],且体积为j最大价值任取物品[0,i−1],体积为(j−物品i的体积)时的最大价值+物品i的价值​
转换为状态转移公式：dp[i][j] = max(dp[i-1][j], dp[i-1][ j-w[i] ] + w[i])

dp 数组最后一个元素即所求的最大价值。

时间复杂为 $O(NV)$。

0-1背包问题模板

模板一：

int 01Package(int[] capacities, int[] worth, int max_capacity) {
        // n 表示物品数量
        int n = capacities.length;
        int[] dp = new int[n][max_capacity + 1];
        // java 默认初始化全部元素为 0，所以只需要初始化第 0 行即可，不需要关心第 0 列
        for (int j = 1; j <= max_capacity; j++) {
            if (j >= capacities[0]) {
                dp[0][j] = worth[0];
            }
        }

        // 从第 1 行和第 1 列开始遍历更新数组
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= max_capacity; j++) {
                // 状态转移方程
	            dp[i][j] = dp[i-1][j];
	            // 防止越界
	            if (j >= capacities[i]) {
	                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-capacities[i]] + worth[i]);    
	            }
            }   
        }
        // 最大价值
        return dp[n-1][max_capacity];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

0-1背包问题模板2【一维滚动数组】：

dp[j] 表示容量为 j 的背包所背的最大价值。
dp 数组初始化为 0。
转移方程为：dp[j] = max(dp[j], dp[j-capacities[i]] + worth[i])。

• 因为二维数组的情况 dp 数组中元素的改变只跟正上方和左上方的数据有关，上下两行数据不相关，所以遍历容量的时候可以正序也可以倒序遍历。而只使用一维数组数组时，若容量正序遍历的时候会造成一个商品选择多次的情况，破坏了上一次选择的状态，倒序的避免了这一情况，每次更新都使用上一层的状态。
• 二维数组先遍历物品和先遍历容量都是可以的，而一维数组先倒序遍历容量的话，结果只能得到满足容量的单个物品价值。

int[] dp = new int[max_capacity + 1];

// 初始化
for (int i = 0; i <= max_capacity; i++) {
	dp[i] = 0;
}

//01背包
for (int i = 0; i < n; i++) {
	// 当前dp[i]要使用上一层左侧的dp值，正序覆盖了上一层左侧的dp值，可能造成多次选取物品的情况，倒叙则避免了这一情况
    for (int j = max_capacity; j >= capacities[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j-capacities[i]] + worth[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 416. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/submissions/
可以把问题抽象为：给定一个数组和一个容量为 sum / 2 的背包，求是否有一种组合能让背包装满。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int x : nums) {
            sum += x;
        }

        if (sum % 2 == 1) {
            return false;
        }
        
        int target = sum / 2;
        
        int[] dp = new int[target + 1];

        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                // 状态转移方程
                dp[j] = Math.max(dp[j], dp[j-num] + num);
            }   
        }
        
        return dp[target] == target;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

LeetCode 494. 目标和

https://leetcode.cn/problems/target-sum/
由于 nums 数组中的元素全为自然数，原问题可转换为：
找到 nums 一个正子集和一个负子集，使得总和等于 target，即

sum(P) - sum(N) = target
sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
2 * sum(P) = target + sum(nums)

最终转换为求 0-1 背包问题：
给定一个数组和一个容量为 (target + sum(nums)) / 2 的背包，求有多少种组合能让背包装满。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 以下三种情况表示无解
        if (sum < target || (sum + target) % 2 == 1 || target + sum < 0) {
            return 0;
        }
        
        int max_capacity = (sum + target) / 2;
        int dp[] = new int[max_capacity + 1];
		
		// 初始化 dp[0] = 1
        dp[0] = 1;

        for (int num : nums) {
            for (int j = max_capacity; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }

        return dp[max_capacity];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

递归回溯法，时间复杂度太高了 $O(2^n)$：

class Solution {
    private int dfs(int[] nums, int start, int S) {
        if (start == nums.length) {
            return S == 0 ? 1 : 0;
        }
        return dfs(nums, start + 1, S + nums[start])
                + dfs(nums, start + 1, S - nums[start]);
    }

    public int findTargetSumWays(int[] nums, int S) {
        return dfs(nums, 0, S);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2. 完全背包问题

有 $N$ 种物品和一个容量为 $V$ 的背包。第 $i$ 件物品的体积是 $C_i$，价值是 $W_i$，每种物品可以重复选择，
求解将物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。

完全背包问题模板

在 0-1 背包问题一维数组解法的基础上，将价值数组正序遍历，表示可以重复选取物品，即可得到完全背包问题的解法。

dp 数组初始化为 0。
转移方程：dp[j] = max(dp[j], dp[j-capacities[i]] + worth[i])

int[] dp = new int[max_capacity + 1];

// 初始化
for (int i = 0; i <= max_capacity; i++) {
	dp[i] = 0;
}
    
//完全背包
for (int i = 0; i < n; i++) {
	// 当前dp[i]要使用上一层左侧的dp值，在上一节的基础上正序遍历，多次选取物品
    for (int j = capacities[i]; j <= max_capacity; j++) {
        dp[j] = Math.max(dp[j], dp[j-capacities[i]] + worth[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 518. 零钱兑换 II

https://leetcode.cn/problems/coin-change-2/
此题与 LeetCode 494. 目标和 类似，求能装满背包的共有多少种装法。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }

        return dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 322. 零钱兑换

https://leetcode.cn/problems/coin-change/
dp[j]： 表示凑足总额为 j 所需钱币的最少个数为 dp[j]。
初始化 dp[0] = 0 表示凑足总额为 0 所需钱币的个数为 0。
初始化 dp[1~amount] = MAX_VALUE 表示没有凑足总额为 1~amount 的钱币搭配。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        dp[0] = 0;

        int MAX_INT = Integer.MAX_VALUE;
        for (int i = 1; i <= amount; i++) {
            dp[i] = MAX_INT;
        }

        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                if (dp[j-coin] != MAX_INT) {
                    dp[j] = Math.min(dp[j], dp[j-coin] + 1);
                }
            }
        }

        return dp[amount] == MAX_INT ? -1 : dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21