代码随想录算法训练营第四十六天|139.单词拆分、多重背包、背包问题总结

题目：139.单词拆分

文章链接：代码随想录

视频链接：LeetCode:139.单词拆分

题目链接：力扣题目链接

图释：

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 将字符串的列表装到set数组中，方便查找find
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        // dp数组表示，装满i个字符串，能否用字符列表装满
        vector<bool> dp(s.size()+1, false);
        dp[0] = true;
        
        // 由于字符串需要按排列循序进行，所以是排列问题: 先遍历背包再遍历物品
        for(int i=1; i<=s.size(); i++){ // 遍历背包  dp[6] = 'leetco'
            // 
            for(int j=0; j<i; j++){ //遍历物品  从j=0开始增加到j=5 
                // 截取字符串  j=4 截取 [4, (6-2)] co
                string word = s.substr(j, i-j); // substr(起始位置，截取个数)
                // 查找 "co"是否在wordSet中， 以及dp[4]='leet'是都为 true
                if(wordSet.find(word) != wordSet.end() && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

题目：多重背包

文章链接：代码随想录

题目链接：卡码网题目链接

图释：将多重背包展开成01背包，每个物品只能用一次

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    for (int i = 0; i < n; i++) cin >> weight[i];
    for (int i = 0; i < n; i++) cin >> value[i];
    for (int i = 0; i < n; i++) cin >> nums[i];

    vector<int> dp(bagWeight + 1, 0);

    for(int i = 0; i < n; i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            for (int k = 1; k <= nums[i] && (j - k * weight[i]) >= 0; k++) { // 遍历个数
                 // k小于物品的数目， k个物品数的重量小于背包的容量
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

    cout << dp[bagWeight] << endl;
}

题目：背包问题总结

文章链接：代码随想录

图释：

1、问能否能装满背包（或者最多装多少）：
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

2、问装满背包有几种方法：
dp[j] += dp[j - nums[i]];

3、问背包装满最大价值：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 

4、问装满背包所有物品的最小个数：
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

遍历顺序：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。