426 开心的金明（零一背包问题）

小灰灰 2022-09-11 04:18 176阅读 0赞

**1. 问题描述：**

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过 N 元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的 N 元。于是，他把每件物品规定了一个重要度，分为 5 等：用整数 1∼5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第 j 件物品的价格为 v\[j\]，重要度为 w\[j\]，共选中了 k 件物品，编号依次为 j1，j2，…，jk，则所求的总和为：   
v\[j1\] × w\[j1\] + v\[j2\] × w\[j2\] +… + v\[jk\] × w\[jk\]  
请你帮助金明设计一个满足要求的购物单。

**输入格式**

输入文件的第 1 行，为两个正整数 N 和 m，用一个空格隔开。（其中 N 表示总钱数，m 为希望购买物品的个数） 从第 2 行到第 m+1 行，第 j 行给出了编号为 j−1 的物品的基本数据，每行有 2 个非负整数 v 和 p。（其中 v 表示该物品的价格，p 表示该物品的重要度）

**输出格式**

输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（数据保证结果不超过 10 ^ 8）。

**数据范围**

1 ≤ N < 30000，  
1 ≤ m < 25，  
0 ≤ v ≤ 10000，  
1 ≤ p ≤ 5

**输入样例：**

1000 5  
800 2  
400 5  
300 5  
400 3  
200 2

**输出样例：**

3900  
来源：[https://www.acwing.com/problem/content/description/428/][https_www.acwing.com_problem_content_description_428]

**2. 思路分析：**

分析题目可以知道每一个物品只能够选或者不选，所以属于经典的**零一背包问题**，使用零一背包的模板编写代码即可，因为使用的是一维数组所以我们逆序遍历体积即可。

**3. 代码如下：**

if __name__ == '__main__':
        V, n = map(int, input().split())
        # 背包的容量相当于是总金额m
        dp = [0] * (V + 1)
        for i in range(n):
            v, p = map(int, input().split())
            for j in range(V, v - 1, -1):
                dp[j] = max(dp[j], dp[j - v] + v * p)
        print(dp[V])

[https_www.acwing.com_problem_content_description_428]: https://www.acwing.com/problem/content/description/428/