算法刷题记录 Day40

算法刷题记录 Day40

Date: 2024.04.06

kamma 56. 多重背包

#include<bits/stdc++.h>
using namespace std;int main(){int n, c;while(cin>>c>>n){vector<int> weights(n, 0);vector<int> values(n, 0);vector<int> knums(n, 0);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>>knums[i];}// dp[j]表示容量为j的背包所能容纳的最高价值vector<int> dp(c+1, 0);for(int i=0; i<n; i++){for(int k=0; k<knums[i]; k++){  //增加一层，遍历同类矿石的个数for(int j=c; j>=weights[i]; j--){dp[j] = max(dp[j], dp[j-weights[i]]+values[i]);}}}cout<<dp[c]<<endl;}}

lc 139. 单词拆分

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {// dp[j] 表示s的前j个字符是否能利用字典中单词拼出。vector<bool> dp(s.size()+1, false);// dp[j] = for(i) dp[j] = dp[j] || (dp[j-wordDict[i].size()] && s.substr(j-wordDict[i].size(), wordDict[i].size()) == wordDict[i])dp[0] = true;// 背包需要在外循环，物品在内循环。因为该问题实际要求的是，各个单词是否能按相同排列组成字符串。所以按排列进行。for(int j=0; j<=s.size(); j++){for(int i=0; i<wordDict.size(); i++){if(j >= wordDict[i].size())dp[j] = dp[j] || (dp[j-wordDict[i].size()] && s.substr(j-wordDict[i].size(), wordDict[i].size()).compare(wordDict[i]) == 0);}}for(int i=0; i<=s.size(); i++){cout<<"i:"<<i<<", dp[i]:"<<dp[i]<<endl;}return dp[s.size()];}
};