九十、动态规划系列背包问题之多重背包
共 4934字，需浏览 10分钟
·
2021-03-14 15:47
「@Author：Runsen」
曾几何时，才记得自己还是大一军训的菜鸟，带着 迷茫和憧憬踏入大学，踏入化工学院，却踏入这个行业，殊不知岁月是最高明的小偷，偷走时间，带走青春，一点线索也不留。大学的玩命学习，一转眼，就大四了，一不小心就成了学校最老的学长！
多重背包
前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。
题目是这样的：来源：https://www.acwing.com/problem/content/4/
有 种物品和一个容量是 的背包。
第 种物品最多有 件，每件体积是，价值是 。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。输出最大价值。
输入格式 第一行两个整数，，，用空格隔开，分别表示物品种数和背包容积。
接下来有 行，每行三个整数 ,,，用空格隔开，分别表示第 种物品的体积、价值和数量。
输出格式 输出一个整数，表示最大价值。
输入样例
4 5
1 2 3 # 体积、价值和数量
2 4 1
3 4 3
4 5 2
输出样例：
10
状态表示：dp[j]
集合：当前价值 j的最大值属性：最大值
多重背包问题的思路跟完全背包的思路非常类似，只是取值是有限制的，因为每件物品的数量是有限制的，状态转移方程为：dp [j] = max(dp [j], dp [j - k*b] + k*w) 这里的b和w指的是当前遍历的体积和价值。
这里一维动态规划和01背包基一样，就是多了一个k的循环，具体的查看下面代码。
n, v = map(int, input().split())
dp = [0 for _ in range(v+1)]
for i in range(n):
b, w, s = map(int, input().split())
for j in range(v, -1, -1):
k = 1
while k <= s and j >= k * b:
dp [j] = max(dp [j], dp [j - k*b] + k*w)
k += 1
print(dp[v])
除了上面的方法，还有用最原始的方法，将多个同一物品转化成不同物品，再用01背包求解
n,v = map(int, input().split())
goods = []
for i in range(n):
goods.append([int(i) for i in input().split()])
new_goods = []
for i in range(n):
for j in range(goods[i][2]):
new_goods.append(goods[i][0:2])
goods = new_goods
n = len(goods)
dp = [0 for i in range(v+1)]
for i in range(n):
# 01背包倒序
for j in range(v,-1,-1):
if j>= goods[i][0]:
dp[j] = max(dp[j], dp[j - goods[i][0]] + goods[i][1])
print(dp[-1])
关于多重背包问题中的二进制解法，Runsen下一篇再写。如今就是体现自己的实力的时候了。Leetcode刷起来。
Leetcode 面试题 17.16. 按摩师
一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。
注意：本题相对原题稍作改动
示例 1：
输入：[1,2,3,1] 输出：4 解释：选择 1 号预约和 3 号预约，总时长 = 1 + 3 = 4。示例 2：
输入：[2,7,9,3,1] 输出：12 解释：选择 1 号预约、 3 号预约和 5 号预约，总时长 = 2 + 9 + 1 = 12。
题目，其实就是不连续最大子序列。
每个预约都可以选择接或不接来做出思考，每次都有两种选择，那么就是状态转移方程：
class Solution:
def massage(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
# 求最值用0
dp = [0] * (len(nums))
dp[0] = nums[0]
for k in range(1,len(nums)):
dp[k] = max(dp[k - 1], nums[k] + dp[k - 2])
return dp[-1]
Leetcode 面试题 08.11. 硬币
硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)
示例1:
输入: n = 5 输出：2 解释: 有两种方式可以凑成总金额: 5=5 5=1+1+1+1+1 示例2:
输入: n = 10 输出：4 解释: 有四种方式可以凑成总金额: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1
class Solution:
def waysToChange(self, n: int) -> int:
# 不就是一个零钱对换问题 的完全背包问题? 这里需要将结果模上 10**9 + 7
# 求最大值
dp = [0] * (n+1)
# f(11) = min(f(10),f(9),f(6)) + 1
dp[0] = 1
for i in [1,5,25,10]:
for j in range(i, n + 1):
dp[j] += dp[j - i]
return dp[-1] % 1000000007
更多的文章
点击下面小程序
- END -