本文共 2904 字，大约阅读时间需要 9 分钟。

@Author：Runsen

曾几何时，才记得自己还是大一军训的菜鸟，带着 迷茫和憧憬踏入大学，踏入化工学院，却踏入这个行业，殊不知岁月是最高明的小偷，偷走时间，带走青春，一点线索也不留。大学的玩命学习，一转眼，就大四了，一不小心就成了学校最老的学长！

前面已经介绍完了01背包和完全背包，今天介绍最后一种背包问题——多重背包。

题目是这样的：来源：https://www.acwing.com/problem/content/4/

有 $N$ 种物品和一个容量是$V$ 的背包。

第 $i$ 种物品最多有 $si$件，每件体积是$Vi$，价值是 $wi$。

求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。

输出最大价值。

输入格式

第一行两个整数，$N$，$V$，用空格隔开，分别表示物品种数和背包容积。

接下来有 $N$ 行，每行三个整数 $Vi$,$wi$,$si$，用空格隔开，分别表示第 $i$ 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

输入样例4 51 2 3 # 体积、价值和数量2 4 13 4 34 5 2输出样例：10

状态表示：dp[j]

1. 集合：当前价值j的最大值
2. 属性：最大值

多重背包问题的思路跟完全背包的思路非常类似，只是取值是有限制的，因为每件物品的数量是有限制的，状态转移方程为：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 += 1print(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_goodsn = 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。

题目，其实就是不连续最大子序列。

每个预约都可以选择接或不接来做出思考，每次都有两种选择，那么就是状态转移方程：

$$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

转载地址：https://maoli.blog.csdn.net/article/details/108622363 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！