背包问题

Posted on Edited on Symbols count in article: 2.7k Reading time ≈ 2 mins.

01背包

经典动态规划问题，输入重量数组weight、价值数组value和背包可承载的最大重量整数maxW 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int knapsack(vector<int>& weight, vector<int>& value, int maxW) {
        // 物品数目
        int kinds = weight.size();
        // dp数组初始化为二维数组
        vector<vector<int>> dp(kinds + 1, vector<int>(maxW + 1, 0));
        // 状态一：可选的目标：0个可选，前一个可选、前两个可选、前三个可选，以此类推（与找零钱不同，物品不能重复选）
        for (int c = 1; c <= kinds; c++) {
            // 状态二：当前的可承载重量，0、1、2...maxW
            for (int w = 1; w <= maxW; w++) {
                // 该物品太大以至于当前重量超标：下标越界，直接赋值为“没有该物品时的最优答案”
                if (w - weight[c - 1] < 0) 
                    dp[c][w] = dp[c - 1][w];
                // 比较，“不选择该物品”和“选择该物品”时，哪个价值大
                else
                    dp[c][w] = max(dp[c - 1][w], dp[c - 1][w - weight[c - 1]] + value[c - 1]);
            }
        }
        return dp[kinds][maxW];
    }
};

完全背包

标准DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n+1, vector<int>(amount+1, 0));
        // base case 这里也可以只dp[0][0]=1，但下面的二重循环的j必须从0开始了
        // 从含义上来说，还是在这里初始化一列全1比较符合定义
        for(int s = 0; s<=n; ++s)
            dp[s][0] = 1;
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=amount; ++j){
                if(coins[i-1] > j)
                    dp[i][j] = dp[i-1][j];
                else // dp[i][j] = dp[i-1][j] + dp[i-1][j-coins[i-1]];一个数字之差就变成不可重复选取了
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }
};

压缩一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1, 0);
        dp[0] = 1;
        for(int i=1; i<=n; ++i){
            for(int j=1; j<=amount; ++j){
                if(coins[i-1] <= j)
                    dp[j] = dp[j] + dp[j-coins[i-1]]; // 由于需要用到当前行更新的值，正好不用倒过来了，和下面子集背包压缩做对比
            }
        }
        return dp[amount];
    }
};

子集背包

标准DP

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
// 子集背包问题
class Solution {
public:
    // sum(A1) == sum(A2) -> target = sum(A)/2
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto e : nums) sum += e;
        if (sum % 2) // 和必须是偶数
            return false;
        int target = sum >> 1;
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, 0)); // 用布尔
        dp[0][0] = 1; // 初始化
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= target; j++) {
                if (nums[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
            }
        }
        return dp[n][target] > 0;
    }
};

压缩一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 子集背包问题
class Solution {
public:
    // sum(A1) == sum(A2) -> target = sum(A)/2
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto e : nums) sum += e;
        if (sum % 2) // 和必须是偶数
            return false;
        int target = sum >> 1;
        int n = nums.size();
        vector<bool> dp(target + 1, false); // 用布尔
        dp[0] = true; // 初始化
        for (int i = 1; i <= n; i++) {
            for (int j = target; j >= 0; j--) { // 必须从后往前，不然会覆盖之前的数据
                if (nums[i - 1] > j)
                    dp[j] = dp[j];
                else
                    dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }
        return dp[target] > 0;
    }
};

参考

labuladong