代码随想录算法训练营第day46|139.单词拆分 、多重背包

目录

139.单词拆分

多重背包

139.单词拆分

力扣题目链接(opens new window)

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。

你可以假设字典中没有重复的单词。

示例 1：

• 输入: s = "leetcode", wordDict = ["leet", "code"]
• 输出: true
• 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

• 输入: s = "applepenapple", wordDict = ["apple", "pen"]
• 输出: true
• 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
• 注意你可以重复使用字典中的单词。

示例 3：

• 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
• 输出: false

思路：可以重复多次使用字典里的单词，属于完全背包，字典里的单词相当于物品，给定的字符串相当于背包；拆分单词顺序不可颠倒，属于求排列，因此外层遍历背包容量，内层遍历物品；如何模拟拆单词的过程呢？将字典里的单词放到一个哈希表（集合）里，遍历的时候依次拆分给定字符串s,如果拆出单词能在字典里找到，则说明拆分成功，dp[i]=true;

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 i=1;i<=s.size();i++){//遍历背包
            for(int j=0;j<=i;j++){//遍历物品
                string word=s.substr(j,i-j);//拆分给定字符串
                if(wordSet.find(word)!=wordSet.end()&&dp[j]==true){
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];

    }
};

多重背包

对于多重背包，我在力扣上还没发现对应的题目，所以这里就做一下简单介绍，大家大概了解一下。

有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

多重背包和01背包是非常像的， 为什么和01背包像呢？

每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

例如：

背包最大重量为10。

物品为：

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

和如下情况有区别么？

毫无区别，这就转成了一个01背包问题了，且每个物品只用一次。

练习题目：卡码网第56题，多重背包(opens new window)

代码如下：

// 超时了
#include<iostream>
#include<vector>
using namespace std;
int main() {
    int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0); 
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    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++) {
        while (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++) { // 遍历物品，注意此时的物品数量不是n
        for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    cout << dp[bagWeight] << endl;
}

大家去提交之后，发现这个解法超时了，为什么呢，哪里耗时呢？

耗时就在 这段代码：

for (int i = 0; i < n; i++) {
    while (nums[i] > 1) { // 物品数量不是一的，都展开
        weight.push_back(weight[i]);
        value.push_back(value[i]);
        nums[i]--;
    }
}

如果物品数量很多的话，C++中，这种操作十分费时，主要消耗在vector的动态底层扩容上。（其实这里也可以优化，先把 所有物品数量都计算好，一起申请vector的空间。

这里也有另一种实现方式，就是把每种商品遍历的个数放在01背包里面在遍历一遍。

代码如下：（详看注释）

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int bagWeight,n;
    cin >> bagWeight >> n;
    vector<int> weight(n, 0);
    vector<int> value(n, 0);
    vector<int> nums(n, 0);
    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];

    vector<int> dp(bagWeight + 1, 0);

    for(int i = 0; i < n; 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]);
            }
        }
    }

    cout << dp[bagWeight] << endl;
}

时间复杂度：O(m × n × k)，m：物品种类个数，n背包容量，k单类物品数量

从代码里可以看出是01背包里面在加一个for循环遍历一个每种商品的数量。 和01背包还是如出一辙的。

当然还有那种二进制优化的方法，其实就是把每种物品的数量，打包成一个个独立的包。

参考：代码随想录