算法训练营第四十六天|139.单词拆分 多重背包

Leetcode139.单词拆分

思路：完全背包，重点在于状态转移方程的条件。

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

多重背包

思路：多重背包问题，将其拆解为01背包即可。

#include<bits/stdc++.h>
using namespace std;
 
void solve(int C, int N){
    vector<int> dp(C + 1);
    vector<int> weight(N);
    vector<int> value(N);
    vector<int> nums(N);
    for (int i = 0; i < N; i++) cin >> weight[i];
    for (int i = 0; i < N; i++) cin >> value[i];
    for (int i = 0; i < N; i++) cin >> nums[i];
     
    for (int i = 0; i < N; i++){
        for (int j = C; j >= weight[i]; j--){
            for (int k = 1; k <= nums[i] && j - k * weight[i] >= 0; k++){
                dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i]);
            }
        }
    }
    cout << dp[C] << endl;
}
 
int main(){
    int C, N;
    cin >> C >> N;
    solve(C, N);
    return 0;
}

第四十六天打卡，这几天对做项目和学习路线有了新的理解和认识，重点不在看多少，在熟悉和掌握，加油！！！