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

139.单词拆分

题目链接：单词拆分

题目描述：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

解题思路：

动规五部曲分析如下：

1. 确定dp数组以及下标的含义
   dp[i]：表示字符串 s前i个字符组成的字符串 s[0…i−1]是否能被拆分成若干个字典中出现的单词

2. 确定递推公式
   每次转移的时候我们需要枚举包含位置i-1的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。使用变量j遍历分割长度为i的字符串，如果字符串[0……j-1]能被字典中的单词拆分并且字符串[j……i-1]在字典中则dp[i]为true。

   dp[i]=dp[j] && check(s[j…i−1])

3. dp数组如何初始化
   dp[0]=true 表示空串且合法。

4. 确定遍历顺序
   先遍历字符串i，再遍历子串在字符串中的终止位置j。

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> dict(wordDict.begin(), wordDict.end());vector<bool> dp(s.size() + 1, false);dp[0] = true;for (int j = 0; j <= s.size(); j++) {for (int i = 0; i < j; i++) {string str = s.substr(i, j - i);if (dict.find(str) != dict.end() && dp[i] == true)dp[j] = true;}}return dp[s.size()];}
};

多重背包问题

题目描述：有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间总和不超过背包容量，且价值总和最大。

解题思想：

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：背包最大重量为10。

物品为：

	重量	价值	数量
物品0	1	15	2
物品1	3	20	3
物品2	4	30	2

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

和如下情况有区别么？

	重量	价值	数量
物品0	1	15	1
物品0	1	15	1
物品1	3	20	1
物品1	3	20	1
物品1	3	20	1
物品2	4	30	1
物品2	4	30	1

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

#include <iostream>
#include <vector>using namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin >> bagWeight>>n;vector<int> weights(n),values(n),nums(n);int x;for (int i = 0; i < n; i++) cin>>weights[i];for (int i = 0; i < n; i++) cin>>values[i];	for (int i = 0; i < n; i++) cin>>nums[i];for (int i = 0; i < n; i++){int num = nums[i];num--;while(num--){weights.push_back(weights[i]);values.push_back(values[i]);}}vector<int> dp(bagWeight+1,0);for (int i = 0; i < weights.size(); i++){for (int j = bagWeight; j>=weights[i];j--){dp[j] = max(dp[j],dp[j-weights[i]]+values[i]);}}cout << dp[bagWeight];}

这里也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。

#include <iostream>
#include <vector>using namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin >> bagWeight>>n;vector<int> weights(n),values(n),nums(n);int x;for (int i = 0; i < n; i++) cin>>weights[i];for (int i = 0; i < n; i++) cin>>values[i];	for (int i = 0; i < n; i++) cin>>nums[i];vector<int> dp(bagWeight+1,0);for (int i = 0; i < weights.size(); i++){for (int j = bagWeight; j>=weights[i];j--){for (int k = 1; k <= nums[i] && (j - k * weights[i]) >= 0; k++)dp[j] = max(dp[j],dp[j-weights[i]*k]+values[i]*k);}}cout << dp[bagWeight];return 0;
}