代码随想录算法训练营第四十六天| 139.单词拆分，56. 携带矿石资源（第八期模拟笔试），背包问题总结

题目链接： 139.单词拆分

思路

代码

题目链接：56. 携带矿石资源（第八期模拟笔试）

思路

代码

总结

题目链接：139.单词拆分

思路

字符串列表中的单词为物品，字符串为背包，单词可重复使用，完全背包问题。本题的字符串有顺序，所以单词必须按照顺序放进字符串中，遍历顺序必须先背包后物品。

①dp数组，字符串长度为j时，dp[j]为true，表示拆分一个或多个在字典中出现的单词

②递推公式，if(字符串s在区间[j,i]的子串出现在字典中 && dp[i] == ture) dp[j] =true

③dp数组初始化，dp[0] = true，其余为false

④遍历顺序，先背包后物品，即先字符串再字符串列表

⑤推导dp数组

代码

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordlist(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        // 先背包后物品
        for (int j = 1; j <= s.size(); j++) {
            for (int i = 0; i < j; i++) {
                string word = s.substr(i, j - i);
                if (wordlist.find(word) != wordlist.end() && dp[i] == true) {
                    dp[j] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

题目链接：56. 携带矿石资源（第八期模拟笔试）

思路

多重背包，每件商品有限次使用，次数大于1，介于01背包和完全背包之间。只需要将次数展开，化为01背包，利用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++) { // 遍历个数
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }

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