算法训练营Day46（动态规划8之多重背包）

本文主要是介绍算法训练营Day46（动态规划8之多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多重背包

关于 多重背包，力扣上没有相关的题目，所以今天的重点就是回顾一波 自己做的背包题目

本题力扣上没有原题，大家可以去卡码网第56题 (opens new window)去练习

简单介绍

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

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

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

说明

多重背包在面试中基本不会出现，力扣上也没有对应的题目，对多重背包的掌握程度知道它是一种01背包，并能在01背包的基础上写出对应代码就可以了

提醒

本题是求排列数，对顺序有要求 

一、动态规划之完全背包（一刷不理解）

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)

这篇关于算法训练营Day46（动态规划8之多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---