效果好的东莞品牌网站建设,wordpress主体中的psd,机械公司简介模板,做旅游宣传不错的网站一、单词拆分
题目一#xff1a;139. 单词拆分
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以…一、单词拆分
题目一139. 单词拆分
139. 单词拆分
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。 定义一个布尔型的动态规划数组dp dp[i]表示字符串s的前i个字符能否被字典wordDict中的一个或多个单词拼接出来 dp[0]为真因为空字符串总是可以被拼接出来的 对于字符串s中的每一个位置i从1到字符串长度遍历i之前的所有位置j从0到i-1检查从j到i的子字符串是否存在于字典wordDict中 /** lc appleetcode.cn id139 langcpp** [139] 单词拆分*/// lc codestart
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring dict(wordDict.begin(), wordDict.end());vectorbool dp(s.length() 1, false);dp[0] true; // 空字符串总是可以被拼接for (int i 1; i s.length(); i) {for (int j 0; j i; j) {if (dp[j] dict.find(s.substr(j, i - j)) ! dict.end()) {dp[i] true;break; // 找到一种拼接方式即可}}}return dp[s.length()];}
};
// lc codeend
二、多重背包
56. 携带矿石资源第八期模拟笔试
时间限制5.000S 空间限制256MB
题目描述
你是一名宇航员即将前往一个遥远的行星。在这个行星上有许多不同类型的矿石资源每种矿石都有不同的重要性和价值。你需要选择哪些矿石带回地球但你的宇航舱有一定的容量限制。
给定一个宇航舱最大容量为 C。现在有 N 种不同类型的矿石每种矿石有一个重量 w[i]一个价值 v[i]以及最多 k[i] 个可用。不同类型的矿石在地球上的市场价值不同。你需要计算如何在不超过宇航舱容量的情况下最大化你所能获取的总价值。
输入描述
输入共包括四行第一行包含两个整数 C 和 N分别表示宇航舱的容量和矿石的种类数量。
接下来的三行每行包含 N 个正整数。具体如下
第二行包含 N 个整数表示 N 种矿石的重量。
第三行包含 N 个整数表示 N 种矿石的价格。
第四行包含 N 个整数表示 N 种矿石的可用数量上限。
输出描述
输出一个整数代表获取的最大价值。 动态规划数组dp[j]表示容量为j的背包所能装下的最大价值。对于每种矿石i遍历背包容量j从大到小更新dp[j] 具体实现步骤如下 对于每种矿石i将其按数量k[i]进行二进制拆分比如如果k[i] 4可以拆分为121共计4个这样就将问题转化为了多个0-1背包问题。对于每个拆分后的矿石更新dp[j]。 #include iostream
#include vector
using namespace std;int main() {int C, N;cin C N;vectorint w(N), v(N), k(N);for (int i 0; i N; i) cin w[i];for (int i 0; i N; i) cin v[i];for (int i 0; i N; i) cin k[i];vectorint dp(C 1, 0);for (int i 0; i N; i) {int num k[i];for (int k 1; num 0; k * 2) { int mul min(k, num);int weight w[i] * mul;int value v[i] * mul;for (int j C; j weight; --j) {dp[j] max(dp[j], dp[j - weight] value);}num - mul;}}cout dp[C] endl;return 0;
}
