代码随想录算法训练营第四十六天| 139.单词拆分 多重背包 背包问题总结篇！

单词拆分 

题目链接：139. 单词拆分 - 力扣（LeetCode）

思路：竟然真能转化为背包问题。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> t(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);//substr(起始位置，截取个数)
                if(t.find(word)!=t.end()&&dp[j]){
                    dp[i]=true;
                }
            }
        }
        return dp[s.size()];

    }
};

关于多重背包，你该了解这些！ 

多重背包和01背包的区别在于一件物品能用多次，且不是不限次。一种处理方法，是将可多次使用的物品当做不同的物品，因此将问题转化为01背包问题。如

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

 但这个方法由于vector的动态扩容十分耗时。还有一种处理方式，就是放到for循环里再遍历一轮

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]);
            }
        }
    }

背包问题总结篇！  

代码随想录 (programmercarl.com)

背包递推公式

• 问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); 
• 问装满背包有几种方法：dp[j] += dp[j - nums[i]] 
• 问背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 
• 问装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]); 

01背包

二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。

完全背包

纯完全背包的一维dp数组实现，先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。

但是仅仅是纯完全背包的遍历顺序是这样的，题目稍有变化，两个for循环的先后顺序就不一样了。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。