简单背包问题小结

87 阅读 0 评论 58 点赞

我是靠谱客的博主积极飞机，这篇文章主要介绍简单背包问题小结，现在分享给大家，希望可以做个参考。

问题陈述

简单的背包问题包括0-1背包问题和完全背包问题。0-1背包问题指的是在可选择项里面，每项最多选择一次，即选择0或者1次。完全背包问题指的是可选择项里面的每项可以选无数次。

做题套路

两层循环，外层是可选择项的每个选项的遍历，里层是背包容量的遍历。在容量增加的情况下，里层的正向遍历会导致重复选择问题，而反序则保证了每个选择最多选择一次。如果0-1背包中每次选项都存在增加或者减少背包容量，则用next数组记录下一步得到的情况，再装回原来的dp数组。

题目

0-1背包问题：

416 分割子集问题
474 一和零
494 目标和

完全背包问题

零钱兑换
零钱兑换2

题目代码

416

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) return false;
        int* dp = new int[sum/2+1];
        for (int i = 0; i <= sum/2; i++) dp[i] = false;
        dp[0] = true;
        for (auto num : nums) {
            for (int i = sum/2; i >= num; i--) {
                dp[i] = dp[i-num] || dp[i];
            }
        }
        return dp[sum/2];
    }
};

474

复制代码

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int** dp = new int*[m+1];
        for (int i = 0; i <= m; i++) {
            dp[i] = new int[n+1];
            for (int j = 0; j <= n; j++) {
                dp[i][j] = 0;
            }
        }
        for (auto str : strs) {
            vector<int> nums;
            if (mp.count(str))
                nums = mp[str];
            else nums = getNums(str);
            for (int i = m; i >= nums[0]; i--) {
                for (int j = n; j >= nums[1]; j--) {
                    dp[i][j] = max(dp[i][j], dp[i-nums[0]][j-nums[1]]+1);
                }
            }
        }
        return dp[m][n];        
    }

vector<int> getNums(string str) {
        int r = 0, c = 0;
        for (auto ch : str) {
            if (ch == '0') r++;
            else if (ch == '1') c++;
        }
        mp[str] = {r,c};
        return {r, c};
    }
private:
    unordered_map<string, vector<int>> mp;  // 不用重复计算字符串的0 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
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int** dp = new int*[m+1];
        for (int i = 0; i <= m; i++) {
            dp[i] = new int[n+1];
            for (int j = 0; j <= n; j++) {
                dp[i][j] = 0;
            }
        }
        for (auto str : strs) {
            vector<int> nums;
            if (mp.count(str))
                nums = mp[str];
            else nums = getNums(str);
            for (int i = m; i >= nums[0]; i--) {
                for (int j = n; j >= nums[1]; j--) {
                    dp[i][j] = max(dp[i][j], dp[i-nums[0]][j-nums[1]]+1);
                }
            }
        }
        return dp[m][n];        
    }

    vector<int> getNums(string str) {
        int r = 0, c = 0;
        for (auto ch : str) {
            if (ch == '0') r++;
            else if (ch == '1') c++;
        }
        mp[str] = {r,c};
        return {r, c};
    }
private:
    unordered_map<string, vector<int>> mp;  // 不用重复计算字符串的0 1个数
};

494

复制代码

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
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        if (S < -1000 || S > 1000) return 0;
        int* dp = new int[2001], *next = new int[2001];
        for (int i = 0; i < 2001; i++) {
            dp[i] = 0;
            next[i] = 0;
        }
        dp[1000] = 1;
        for (auto num : nums) {
            for (int i = 0; i < 2001; i++) {
                if (dp[i]) {
                    if (i-num >= 0) next[i-num] += dp[i];
                    if (i+num < 2001) next[i+num] += dp[i];
                }
            }
            for (int i = 0; i < 2001; i++) {
                dp[i] = next[i];
                next[i] = 0;
            }
        }
        return dp[1000+S];
    }
};

322

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int* dp = new int[amount+1];
        for (int i = 0; i <= amount; i++) dp[i] = amount+1;
        dp[0] = 0;
        for (auto coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = min(dp[i], dp[i-coin]+1);
            }
        }
        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
};

零钱兑换2

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        reverse(coins.begin(), coins.end());
        if (amount == 0) return 1;
        int* dp = new int[amount+1];
        for (int i = 0; i <= amount; i++) dp[i] = 0;
        dp[0] = 1;
        for (auto coin : coins) {
            for (int j = 1; j <= amount; j++) {
                if (j >= coin)
                    dp[j] += dp[j-coin]; 
            }
        }
        return dp[amount];
    }
};