算法刷题记录 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()];
    }
};