RQNOJ-PID2 / 开心的金明

小灰灰 2022-08-09 12:59 143阅读 0赞

PID2 / 开心的金明 ☆

*  [提交你的代码][Link 1]
 *  [查看讨论和题解][Link 2]

![blank.png][]

34秒前

我的状态

已通过

2015-10-25 15:26:03

运行耗时：95 ms

运行内存：12372 KB

查看最后一次评测记录

![36_lightgrey_circle_status.png][]

![static.png][]

质量 8

题目评价

质量

★★★★★

★★★★☆

★★★☆☆

★★☆☆☆

★☆☆☆☆

62.5%

7.1%

3.5%

19.6%

★

☆

![button-check.png][]

通过人数 8298 / 25255

通过统计

最短耗时

0ms

最小内存

0KB

![tag.png][]

动态规划

题目标签

类型

[动态规划][Link 3]

来源

[NOIP2006普及组][NOIP2006]

**题目描述**

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

输入：

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

输出：

3900

简单的01背包问题，将钱看成是背包容量，要求的最大的是 物品的价格和重要度乘积！

代码：

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int f[31000],val[30],weight[30];
    int main()
    {
    	int i,j,M,N,v,p;
    	scanf("%d%d",&M,&N);
    	for(i=0;i<N;i++)
    	{
    		scanf("%d%d",&v,&p);
    		weight[i]=v;
    		val[i]=v*p;
    	}
    	memset(f,0,sizeof(f));
    	for(i=0;i<N;i++)
    	{
    		for(j=M;j>=weight[i];j--)
    		{
    			f[j]=max(f[j],f[j-weight[i]]+val[i]);
    		}
    	}
    	printf("%d\n",f[M]);
    	return 0;
     }

[Link 1]: http://www.rqnoj.cn/problem/2#problem-submit
[Link 2]: http://www.rqnoj.cn/problem/2#problem-detail-talk
[blank.png]: /images/20220731/7c6ea0095a4d4ce48908042ea3ad3201.png
[36_lightgrey_circle_status.png]: /images/20220731/f36ac2cca1434c42b7c863f56a990bfd.png
[static.png]: /images/20220731/287757875aad4943909c62cbe6052ad5.png
[button-check.png]: /images/20220731/62ba9e363e394d35a6c5e63dd21e4ba9.png
[tag.png]: /images/20220731/c50ad40ef05c4dbb960c9ad2a93c480b.png
[Link 3]: http://www.rqnoj.cn/tags/11
[NOIP2006]: http://www.rqnoj.cn/tags/551