建个网站需要投资多少,广州网页设计师培训班,wordpress最好的免费主题2018,门户网站关键词多重背包
关于 多重背包#xff0c;力扣上没有相关的题目#xff0c;所以今天的重点就是回顾一波 自己做的背包题目
本题力扣上没有原题#xff0c;大家可以去卡码网第56题 (opens new window)去练习
简单介绍
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用力扣上没有相关的题目所以今天的重点就是回顾一波 自己做的背包题目
本题力扣上没有原题大家可以去卡码网第56题 (opens new window)去练习
简单介绍
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用每件耗费的空间是Ci 价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量且价值总和最大。
多重背包和01背包是非常像的 为什么和01背包像呢
每件物品最多有Mi件可用把Mi件摊开其实就是一个01背包问题了。
说明
多重背包在面试中基本不会出现力扣上也没有对应的题目对多重背包的掌握程度知道它是一种01背包并能在01背包的基础上写出对应代码就可以了 139.单词拆分 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 提醒
本题是求排列数对顺序有要求 一、动态规划之完全背包一刷不理解
class Solution:def wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict)n len(s)dp [False] * (n 1) # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词dp[0] True # 初始状态空字符串可以被拆分成单词for i in range(1, n 1): # 遍历背包for j in range(i): # 遍历单词if dp[j] and s[j:i] in wordSet:dp[i] True # 如果 s[0:j] 可以被拆分成单词并且 s[j:i] 在单词集合中存在则 s[0:i] 可以被拆分成单词breakreturn dp[n]
疑惑
为什么要 dp[0] 表示空字符串
递推公式的推导
二、回溯算法
class Solution:def backtracking(self, s: str, wordSet: set[str], startIndex: int) - bool:# 边界情况已经遍历到字符串末尾返回Trueif startIndex len(s):return True# 遍历所有可能的拆分位置for i in range(startIndex, len(s)):word s[startIndex:i 1] # 截取子串if word in wordSet and self.backtracking(s, wordSet, i 1):# 如果截取的子串在字典中并且后续部分也可以被拆分成单词返回Truereturn True# 无法进行有效拆分返回Falsereturn Falsedef wordBreak(self, s: str, wordDict: List[str]) - bool:wordSet set(wordDict) # 转换为哈希集合提高查找效率return self.backtracking(s, wordSet, 0) 背包问题总结篇 代码随想录 一刷没时间二刷再来进行总结
