网站开发师培训,大型网站制作教程,西安最新出行政策,新手建立企业网站流程背包问题要结束了#xff01;首先是今天的练习题#xff0c;然后是多重背包的知识点#xff0c;最后对这几天背包问题做一个总结#xff01;
1. 练习题
139. Word Break Given a string s and a dictionary of strings wordDict, return true if s can be segmented into…背包问题要结束了首先是今天的练习题然后是多重背包的知识点最后对这几天背包问题做一个总结
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循环遍历物品。 背包问题最关键的两部递推公式和遍历顺序。
