Day46 动态规划part08 139.单词拆分 多重背包

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {unordered_set<string> wordSet(wordDict.begin(), wordDict.end());vector<bool> dp(s.size()+1,false); //dp[i]含义是字符串长度为i,能否单词拆分dp[0] = 1;for(int j = 0; j<=s.size();j++){for(int i = 0; i<j;i++){string word = s.substr(i,j-i);if(wordSet.find(word)!= wordSet.end()&&dp[i]) dp[j] = true;}}/*for(int i = 0; i<s.size();i++){for(int j = i; j<=s.size();j++){string word = s.substr(i,j-i);if(wordSet.find(word)!= wordSet.end()&&dp[i]) dp[j] = true;}}*/return dp[s.size()];}
};

将问题转化为01背包求解

#include<iostream>
#include<vector>
using namespace std;int main(){int C, N;cin>>C>>N;vector<int> weights(N);vector<int> values(N);vector<int> nums(N);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(C+1);for(int i = 0;i<N;i++){for(int j = C; j >=weights[i];j--){for(int k=1; k<=nums[i]&&j-k*weights[i]>=0;k++){dp[j] = max(dp[j],dp[j-k*weights[i]]+k*values[i]);}}}std::cout << dp[C] << std::endl;return 0;
}