JLUVicent

139单词拆分&多重背包&背包总结

 
  • 2023年 04月01日
  • 0 阅读

day46

139.单词拆分

题目链接：139. 单词拆分

解题思路：参考 视频

回溯暴搜

// 回溯暴搜超时
class Solution {
public:
    bool backtracking( const string& s,const unordered_set<string>& wordset,int startIndex){
        if( startIndex >= s.size()){
            return true;
        }

        for( int i = startIndex;i < s.size(); i++){
            string word = s.substr(startIndex,i-startIndex+1);
            if( wordset.find(word) != wordset.end() && backtracking(s,wordset,i+1)){
                return true;
            }
        }
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordset(wordDict.begin(),wordDict.end());
        return backtracking( s,wordset,0);
    }   
};

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

动态规划

单词是物品，字符串s是背包

动态规划五部曲：

1.确定dp[j]下标及含义： dp[j]表示字符串长度为j的话,dp[j]为true

2.确定递推公式：如果dp[i]为true，且[i,j]区间的子串出现在这个字典中，dp[j]一定时true(i<j).

3.初始化：dp[0] = true,剩下都是false;

4.确定遍历顺序：本题相当于排列问题，先背包再物品

for( int j = 0; j <= s.size(); j++ ){
    for( int i = 0; i < j; i++){
        string word = s.substr(i,j-i+1);
        if( wordset.find(word) != wordset.end() && dp[i]){
           dp[j] = true;
        }
    }
}

5.打印dp数组

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[0] = true;
        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;
                }
            }
        }
        return dp[s.size()];
    }   
};

多重背包

多重背包可以直接转换为01背包，如下：

背包最大重量为10。

物品为：

  重量 价值 数量
物品0 1 15 2
物品1 3 20 3
物品2 4 30 2

问背包能背的物品最大价值是多少？

和如下情况有区别么？

  重量 价值 数量
物品0 1 15 1
物品0 1 15 1
物品1 3 20 1
物品1 3 20 1
物品1 3 20 1
物品2 4 30 1
物品2 4 30 1

没有任何区别，leetcode上找不到多重背包的题目

总结：将多重背包转换为01背包即可

// 时间复杂度：O(m*n*k)，m为物品的种类，n背包容量,k单个物品数量
void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    for (int i = 0; i < nums.size(); i++) {
        while (nums[i] > 1) { // nums[i]保留到1，把其他物品都展开
            weight.push_back(weight[i]);
            value.push_back(value[i]);
            nums[i]--;
        }
    }

    vector<int> dp(bagWeight + 1, 0);
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;

}
int main() {
    test_multi_pack();
}

另外一种方式

void test_multi_pack() {
    vector<int> weight = {1, 3, 4};
    vector<int> value = {15, 20, 30};
    vector<int> nums = {2, 3, 2};
    int bagWeight = 10;
    vector<int> dp(bagWeight + 1, 0);


    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            // 以上为01背包，然后加一个遍历个数
            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]);
            }
        }
        // 打印一下dp数组
        for (int j = 0; j <= bagWeight; j++) {
            cout << dp[j] << " ";
        }
        cout << endl;
    }
    cout << dp[bagWeight] << endl;
}
int main() {
    test_multi_pack();
}

背包总结

动态规划五部曲：

1.确定dp[j]及下标的含义：这里一直用j就不改了

2.确定递推公式

3.dp数组初始化

4.确定遍历顺序

5.打印dp数组

1

搜索