class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
# 求排列先遍历背包再遍历物品
for i in range(len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in wordDict:
dp[i] = True # dp[j] 可以被拆分单词，并且 s[j:i] 在字典中。s[0:i] 也可以被拆分单词
break
return dp[len(s)]
[多重背包]
有N种物品和一个容量为V 的背包。第i种物品最多有Mi件可用，每件耗费的空间是Ci ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。
def multi_bag(weight, value, count, bag_weight):
dp = [0] * (bag_weight + 1)
for i in range(len(weight)): # 先遍历物品
for j in range(bag_weight, weight[i] - 1, -1): # 再遍历背包
# 遍历个数
for k in range(1, count[i] + 1):
if j - k * weight[i] >= 0:
dp[j] = max(dp[j], dp[j - k * weight[i]] + k * value[i])
# 打印 dp
print(" ".join([str(dp[j]) for j in range(bag_weight + 1)]))
return dp[bag_weight]
if __name__ == "__main__":
weight = [1, 3, 4]
value = [15, 20, 30]
bag_weight = 4
count = [2, 3, 2]
res = multi_bag(weight, value, count, bag_weight)
print(res)