(46/60)单词拆分、多重背包

day46

单词拆分

leetcode：139. 单词拆分

动态规划

代码实现

/*
意义：长度为j的字符串能否被dict里的单词拼出为dp[j]
递推：if(dp[j] && j~i子串在dict里) dp[i] = true;
初始化：dp[0] = true 无意义，只是滚雪球起点;其余为false
遍历：对顺序有要求，排列数，先背包后物品；可重复取，正序
*/

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

        return dp[s.size()];
    }
};

多重背包

卡码网：携带矿石资源（第八期模拟笔试）

动态规划

思路

多重背包就是把同类型的物品拆包出来，转化为0-1背包。

代码实现

/*
意义：dp[j]
*/

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
    int C = 0;  // capacity
    int N = 0;  // types
    cin>>C;cin>>N;
    vector<int> weight(N,0);
    vector<int> value(N,0);
    vector<int> nums(N,0);
    for(int i = 0;i < 3;i++){
        for(int j = 0;j < N;j++){
            if(i == 0)  cin>>weight[j];
            else if(i == 1) cin>>value[j];
            else if(i == 2) cin>>nums[j];
        }
    }
    
    // 有多个同类型的拆包
    for(int i = 0;i < N;i++){
        while(nums[i] > 1){
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }

    
    
    vector<int> dp(C+1,0);
    // 0-1背包。先物品再背包；倒序
    // 注意现在的物品数量应该是size()
    for(int i = 0;i < weight.size();i++){
        for(int j = C;j >= weight[i];j--){
            dp[j] = max(dp[j],dp[j - weight[i]] + value[i]);
        }
    }
    
    cout<<dp[C];
    
    
    return 0;
}

背包总结