代码随想录算法训练营Day46 | 动态规划(8/17) 1.练习题 LeetCode 139.单词拆分 2.多重背包 3. 背包问题总结篇！

背包问题要结束了！首先是今天的练习题，然后是多重背包的知识点，最后对这几天背包问题做一个总结！

1. 练习题

139. Word Break

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包！

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        dp = [False]*(len(s) + 1)
        dp[0] = True 
        for j in range(1, len(s) + 1):
            for word in wordDict:
                if j >= len(word):
                    dp[j] = dp[j] or (dp[j - len(word)] and word == s[j - len(word):j])
        return dp[len(s)]

2. 多重背包

N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
多重背包和01背包是非常像的， 为什么和01背包像呢？
每件物品最多有Mi件可用，把Mi件摊开，其实就是一个01背包问题了。

但面试不会考，LeetCode也没有相关题目
 

3. 背包问题总结

背包问题是动态规划里的非常重要的一部分！

3.1 背包递推公式

问能否能装满背包（或者最多装多少）：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]);

3.2 遍历顺序

3.2.1 01背包

二维dp数组01背包先遍历物品还是先遍历背包都是可以的，且第二层for循环是从小到大遍历。
一维dp数组01背包只能先遍历物品再遍历背包容量，且第二层for循环是从大到小遍历。
一维dp数组的背包在遍历顺序上和二维dp数组实现的01背包其实是有很大差异的，这点需要注意！

3.2.2 完全背包

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
背包问题最关键的两部：递推公式和遍历顺序。