1019 庆功会（多重背包问题）

ゝ一世哀愁。 2022-09-11 00:04 131阅读 0赞

**1. 问题描述：**

为了庆贺班级在校运动会上取得全校第一名成绩，班主任决定开一场庆功会，为此拨款购买奖品犒劳运动员。期望拨款金额能购买最大价值的奖品，可以补充他们的精力和体力。

**输入格式**

第一行二个数n，m，其中n代表希望购买的奖品的种数，m表示拨款金额。接下来n行，每行3个数，v、w、s，分别表示第I种奖品的价格、价值（价格与价值是不同的概念）和能购买的最大数量（买0件到s件均可）。

**输出格式**

一行：一个数，表示此次购买能获得的最大的价值（注意！不是价格）。

**数据范围**

n ≤ 500，m ≤ 6000,  
v ≤ 100，w ≤ 1000，s ≤ 10

**输入样例：**

5 1000  
80 20 4  
40 50 9  
30 50 7  
40 30 6  
20 20 1

**输出样例：**

1040  
来源：[https://www.acwing.com/problem/content/1021/][https_www.acwing.com_problem_content_1021]

**2. 思路分析：**

分析题目我们可以知道这道题目的本质是**[多重背包问题][Link 1]**（裸题），我们可以将拨款金额m看成是背包的容量，奖品的价格看成是物品的体积，奖品的价值看成是物品的价值，我们需要在不超过背包容量的前提下使得背包的价值最大。因为数据规模不是特别大所以直接使用朴素版的多重背包问题写法解决即可。

**3. 代码如下：**

if __name__ == '__main__':
        n, V = map(int, input().split())
        dp = [0] * (V + 1)
        for i in range(n):
            # v表示第i种物品的价格, w表示第i种物品的价值, s表示第i种物品的上限
            v, w, s = map(int, input().split())
            for j in range(V, -1, -1):
                for k in range(s + 1):
                    if k * v <= j:
                        dp[j] = max(dp[j], dp[j - k * v] + k * w)
                    else: break
        print(dp[V])

[https_www.acwing.com_problem_content_1021]: https://www.acwing.com/problem/content/1021/
[Link 1]: https://blog.csdn.net/qq_39445165/article/details/120211348