Posted Updated Leetcode24 minutes read (About 3540 words)0 visits

背包问题总结

背包问题主要分为01背包和完全背包问题。
思路上转载from背包九讲。

01背包

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：

1
2
3
for i=1..N
    for v=V..0
        f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。
如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。
为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。
这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

实战

Lintcode 92. Backpack：01背包，背包不含价值，求背包能装的最大量。
这是最简单的01背包问题，状态转移方程是：W[i][j] = max(W[i-1][j], W[i-1][j-A[i]]+a[i])
时间空间复杂度都是O(mn)

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
Example 1:
	Input:  [3,4,8,5], backpack size=10
	Output:  9

Example 2:
	Input:  [2,3,5,7], backpack size=12
	Output:  12
*/

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int len = A.length;
        if(A==null ||  len==0){
            return 0;
        }
        int[][] dp = new int[len+1][m+1];
        for(int i = 0;i<=len;i++){
            dp[i][0] = 0;
        }
        for(int i = 0;i<=m;i++){
            dp[0][i] = 0;
        }
        
        for(int i = 1;i<=len;i++){
            for(int j = 1;j<=m;j++){
                int buyValue = j-A[i-1]>=0?(dp[i-1][j-A[i-1]]+A[i-1]):0;
                dp[i][j] = Math.max(dp[i-1][j], buyValue);
            }
        }
        
        return dp[len][m];
    }
}

可以进一步优化时间复杂度，从状态转移方程中我们可以看到，每一个W[i][j]其实只和W[i-1][j]及W[i-1][j-A[i]]有关，也就是说与上一行的左侧有关，所以如果我们只想用一个一维数组而不是二维数组的话，我们应该从数组的尾部不断向头部进行计算，这样保证我们每次拿到的都是i-1的值。这样空间复杂度减为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        if(A==null || A.length==0)
            return 0;
        int len = A.length;
        int[] dp = new int[m+1];
        dp[0] = 0;
        for(int i = 1;i<=len;i++){
            for(int j = m;j>=1;j--){
                int buyValue = j-A[i-1]>=0?(dp[j-A[i-1]]+A[i-1]):0;
                dp[j] = Math.max(dp[j], buyValue);
            }
        }
        return dp[m];
    }
}

Lintcode 125. Backpack II：与上一道题基本完全相同，只不过多加了一个商品的价值，求的是最大的商品价值。
状态转移方程是：W[i][j] = max(W[i-1][j], W[i-1][j-A[i]]+V[i])

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
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        if(A==null || A.length==0){
            return 0;
        }
        
        int len = A.length;
        int[] dp = new int[m+1];
        dp[0] = 0;
        for(int i = 1;i<=len;i++){
            for(int j = m;j>=1;j--){
                int buyValue = j-A[i-1]>=0?dp[j-A[i-1]]+V[i-1]:0;
                dp[j] = Math.max(dp[j], buyValue);
            }
        }
        
        return dp[m];
    }
}
  1. Partition Equal Subset Sum: 这道题被转化为：总重量为sum/2，能装的最大重量的01背包问题，与第一题相同。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
416. Partition Equal Subset Sum
Medium

1627

50

Favorite

Share
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.
 

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
 

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
*/
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int num:nums){
            sum += num;
        }
        
        if(sum%2!=0){
            return false;
        }
        
        int partitionSum = sum/2;
        int max = partitionSum + 1;
        int len = nums.length;
        int[] dp = new int[partitionSum+1];
        dp[0] = 0;
        for(int i = 1;i<=dp.length-1;i++){
            dp[i] = 0;
        }
        
        for(int i = 1;i<=len;i++){
            for(int j = partitionSum;j>=1;j--){
                int value = j>=nums[i-1]?(dp[j-nums[i-1]]+nums[i-1]):0;
                dp[j] = Math.max(value, dp[j]);
            }
        }
        
        
        if(dp[partitionSum]==partitionSum){
            return true;
        }
        
        return false;
    }
}
  1. Target Sum : 这道题可以转化成01背包来做。
    https://leetcode.com/problems/target-sum/discuss/97334/Java-(15-ms)-C%2B%2B-(3-ms)-O(ns)-iterative-DP-solution-using-subset-sum-with-explanation
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
494. Target Sum
Medium

1720

81

Favorite

Share
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Example 1:
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 3.
Note:
The length of the given array is positive and will not exceed 20.
The sum of elements in the given array will not exceed 1000.
Your output answer is guaranteed to be fitted in a 32-bit integer.
*/
class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int num:nums){
            sum = sum + num;
        }
        
        if((sum+S)%2!=0){
            return 0;
        }
        
        if(sum<S){
            return 0;
        }
        
        int backpack = (sum+S)/2;
        int len = nums.length;
        int[] dp = new int[backpack+1];
        dp[0] = 1;
        for(int i = 1;i<=len;i++){
            for(int j = backpack;j>=0;j--){
                int value = j>=nums[i-1]?dp[j-nums[i-1]]:0;
                dp[j] = value + dp[j];
            }
        }
        
        return dp[backpack];
        
        
    }
}
  1. Ones and Zeroes : 01背包问题

完全背包

题目

有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路

这个问题非常类似于01背包问题，所不同的是每种物品有无限件。也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路，令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程，像这样：f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}，这跟01背包问题一样有O(VN)个状态需要求解，但求解每个状态的时间已经不是常数了，求解状态f[i][v]的时间是O(v/c[i])，总的复杂度可以认为是O(V*Σ(V/c[i]))，是比较大的。
将01背包问题的基本思路加以改进，得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要，可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

转化为01背包问题求解

既然01背包问题是最基本的背包问题，那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是，考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度，但这毕竟给了我们将完全背包问题转化为01背包问题的思路：将一种物品拆成多件物品。
更高效的转化方法是：把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品，其中k满足c[i]*2^k<=V。这是二进制的思想，因为不管最优策略选几件第i种物品，总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品，是一个很大的改进。
但我们有更优的O(VN)的算法。

O(VN)的算法

这个算法使用一维数组，先看伪代码：

1
2
3
for i=1..N
    for v=0..V
        f[v]=max{f[v],f[v-cost]+weight}

你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

实战

  1. Coin Change: 完全背包问题，同时要注意初始化思路(见前面01背包的总结)。

未优化写法

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
322. Coin Change
Medium

2439

87

Favorite

Share
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.
*/
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins==null || coins.length==0){
            return 0;
        }
        
        int max = amount+1;
    
        int len = coins.length;
        int[][] dp = new int[len+1][amount+1];
        for(int i = 0;i<=len;i++){
            dp[i][0] = 0;
        }
        
        for(int i = 1;i<=amount;i++){
            dp[0][i] = max;
        }
        
        
        for(int i = 1;i<=len;i++){
            for(int j = 1;j<=amount;j++){
                int value = (j-coins[i-1]>=0)?(dp[i][j-coins[i-1]]+1) : max;
                dp[i][j] = Math.min(value, dp[i-1][j]);
            }
        }
        
        
        if(dp[len][amount]<max){
            return dp[len][amount];
        }
        
        return -1;
    }
}

空间复杂度优化后的写法

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
27
class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins==null || coins.length==0){
            return 0;
        }
        int max = amount+1;
        int len = coins.length;
        int[] dp = new int[amount+1];
        dp[0] = 0;
        for(int i = 1;i<=dp.length-1;i++){
            dp[i] = max;
        }
        
        for(int i = 1;i<=len;i++){
            for(int j = 1;j<=amount;j++){
                int value = (j>=coins[i-1]?(dp[j-coins[i-1]]):max)+1;
                dp[j] = Math.min(value, dp[j]);
            }
        }
        
        if(dp[amount]<max){
            return dp[amount];
        }
        
        return -1;
    }
}
Follow

Catalogue

×