洛谷P1060 开心的金明（标准01背包）

分手后的思念是犯贱 2022-05-28 04:49 178阅读 0赞

## 题目描述 ##

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过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（<30000）表示总钱数，m（<25）为希望购买物品的个数。）

从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数

v p （其中v表示该物品的价格(v<=10000)，p表示该物品的重要度(1~5)）

输出格式：

输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（<100000000）。

## 输入输出样例 ##

输入样例\#1： 复制

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

输出样例\#1： 复制

3900

## 说明 ##

NOIP 2006 普及组 第二题

裸的01背包问题

讲解如下：

![70][]

![70 1][]

AC代码：

#include<iostream>
    using namespace std;
    #define Maxn 30005
    int  w[Maxn];//质量,即题目中的价钱
    int  v[Maxn];//价值,即题目中的重要度
    int N;//背包总容量,即题目中的最多能花的钱数
    int m;//物品数量
    int g[Maxn];
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	cin >> N >> m;
    	for (int i = 1; i <= m; i++)
    	{
    		cin >> w[i] >> v[i];
    		v[i] *= w[i];//按题目要求价值为重要度乘价格
    	}
    
    	//核心部分
    	for (int i = 1; i <= m; i++)
    	{
    		//for (int k = N; k >= 1; k--) //此处换成k>=1一样能过，是因为数据很水吗？
    		for (int k = N; k >= w[i]; k--)
    		{
    			if (k > w[i])
    			{
    				int pt = g[k - w[i]] + v[i];
    				if (pt > g[k])
    					g[k] = pt;
    			}
    		}
    	}
    	cout << g[N];
    	return 0;
    }

[70]: /images/20220528/2fde509a9b1444e3aaa996eecc760c6b.png
[70 1]: /images/20220528/cac19b2793a64de0a45bd8e2e54d4292.png