九十、动态规划系列背包问题之多重背包
共 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 -