九十、动态规划系列背包问题之多重背包
【摘要】 @Author:Runsen
曾几何时,才记得自己还是大一军训的菜鸟,带着 迷茫和憧憬踏入大学,踏入化工学院,却踏入这个行业,殊不知岁月是最高明的小偷,偷走时间,带走青春,一点线索也不留。大学的玩命学习,一转眼,就大四了,一不小心就成了学校最老的学长!
前面已经介绍完了01背包和完全背包,今天介绍最后一种背包问题——多重背包。
题目是这样的:来源:htt...
@Author:Runsen
曾几何时,才记得自己还是大一军训的菜鸟,带着 迷茫和憧憬踏入大学,踏入化工学院,却踏入这个行业,殊不知岁月是最高明的小偷,偷走时间,带走青春,一点线索也不留。大学的玩命学习,一转眼,就大四了,一不小心就成了学校最老的学长!
前面已经介绍完了01背包和完全背包,今天介绍最后一种背包问题——多重背包。
题目是这样的:来源:https://www.acwing.com/problem/content/4/
有 N N N 种物品和一个容量是 V V V 的背包。
第 i i i 种物品最多有 s i si si件,每件体积是 V i Vi Vi,价值是 w i wi wi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
输入格式
第一行两个整数, N N N, V V V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N N N 行,每行三个整数 V i Vi Vi, w i wi wi, s i si si,用空格隔开,分别表示第 i i i 种物品的体积、价值和数量。
输出格式
输出一个整数,表示最大价值。
输入样例
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。
题目,其实就是不连续最大子序列。
每个预约都可以选择接或不接来做出思考,每次都有两种选择,那么就是状态转移方程:
d p [ k ] = m a x ( d p [ k − 1 ] , n u m s [ k ] + d p [ k − 2 ] ) dp[k] = max(dp[k - 1], nums[k ] + dp[k - 2]) dp[k]=max(dp[k−1],nums[k]+dp[k−2])
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
文章来源: maoli.blog.csdn.net,作者:刘润森!,版权归原作者所有,如需转载,请联系作者。
原文链接:maoli.blog.csdn.net/article/details/108622363
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论(0)