单词拆分

题目链接🔗

单词是物品，字符串s是背包，单词能否组成字符串s就是问物品能不能装满背包。

拆分时可以重复使用字典中的单词，就是完全背包。

1. 确定dp数组和下标含义

dp[i]: 字符串长度为i，dp[i]为true，表示可以拆分成一个或者多个在字典中出现的单词。

2. 确定递推公式

如果确定dp[j] == true，且[j, i]这个区间的子串出现在字典里，那么dp[i] = true。

递推公式就是，如果[j, i] 这个区间的子串出现在字典里 && dp[j]是true，那么 dp[i] = true。

3. dp数组如何初始化

dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

下标非0的dp[i]初始化为false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

4. 确定遍历顺序

三个样例说明物品之间有顺序，所以求的是排列数。

先遍历背包再遍历物品。

5. 举例推导dp[i]

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= s.size(); i++) {   // 遍历背包
            for (int j = 0; j < i; j++) {       // 遍历物品
                string word = s.substr(j, i - j); //substr(起始位置，截取的个数)
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = 1;
                }
            }
        }
        return dp[s.size()];
    }
};

多重背包理论基础

有$N$种物品和一个容量为$V$的背包。第$i$种物品最多有$M_i$件可用，每件耗费的空间是$C_i$ ，价值是$W_i$ 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的，把$M_i$件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

问背包能背的物品最大价值是多少？

#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;
}