海宁做网站,北京网站建设方案托管,页面跳转自动升级,灌云网站建设维护139.单词拆分 题目链接#xff1a;单词拆分 题目描述#xff1a;给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 **注意#xff1a;**不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词… 139.单词拆分 题目链接单词拆分 题目描述给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 **注意**不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 解题思路
动规五部曲分析如下 确定dp数组以及下标的含义 dp[i]表示字符串 s前i个字符组成的字符串 s[0…i−1]是否能被拆分成若干个字典中出现的单词 确定递推公式 每次转移的时候我们需要枚举包含位置i-1的最后一个单词看它是否出现在字典中以及除去这部分的字符串是否合法即可。使用变量j遍历分割长度为i的字符串如果字符串[0……j-1]能被字典中的单词拆分并且字符串[j……i-1]在字典中则dp[i]为true。 dp[i]dp[j] check(s[j…i−1]) dp数组如何初始化 dp[0]true 表示空串且合法。 确定遍历顺序 先遍历字符串i再遍历子串在字符串中的终止位置j。
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring dict(wordDict.begin(), wordDict.end());vectorbool 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。
物品为
重量价值数量物品01152物品13203物品24302
问背包能背的物品最大价值是多少
和如下情况有区别么
重量价值数量物品01151物品01151物品13201物品13201物品13201物品24301物品24301
毫无区别这就转成了一个01背包问题了且每个物品只用一次。
#include iostream
#include vectorusing namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin bagWeightn;vectorint weights(n),values(n),nums(n);int x;for (int i 0; i n; i) cinweights[i];for (int i 0; i n; i) cinvalues[i]; for (int i 0; i n; i) cinnums[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]);}}vectorint dp(bagWeight1,0);for (int i 0; i weights.size(); i){for (int j bagWeight; jweights[i];j--){dp[j] max(dp[j],dp[j-weights[i]]values[i]);}}cout dp[bagWeight];}这里也有另一种实现方式就是把每种商品遍历的个数放在01背包里面在遍历一遍。
#include iostream
#include vectorusing namespace std;
int main(int argc, char *argv[]) {int bagWeight, n;cin bagWeightn;vectorint weights(n),values(n),nums(n);int x;for (int i 0; i n; i) cinweights[i];for (int i 0; i n; i) cinvalues[i]; for (int i 0; i n; i) cinnums[i];vectorint dp(bagWeight1,0);for (int i 0; i weights.size(); i){for (int j bagWeight; jweights[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;
}
