Description

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过\(N\)元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的\(N\)元。于是，他把每件物品规定了一个重要度，分为\(5\)等：用整数\(1-5\)表示，第\(5\)等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过\(N\)元（可以等于\(N\)元）的前提下，使每件物品的价格与重要度的乘积的总和最大。

设第\(j\)件物品的价格为\(v[j]\)，重要度为\(w_[j]\)，共选中了\(k\)件物品，编号依次为\(j_1,j_2,…,j_k\)则所求的总和为：

\(v_[j_1] \times w_[j_1]+v_[j_2] \times w_[j_2]+ …+v_[j_k] \times w_[j_k]\)。

请你帮助金明设计一个满足要求的购物单。

Input

第一行，为\(2\)个正整数，用一个空格隔开：\(N ,m\)

（其中\(N<30000\)表示总钱数，\(m<25\)为希望购买物品的个数。）

从第\(2\)行到第\(m+1\)行，第\(j\)行给出了编号为\(j-1\)的物品的基本数据，每行有\(2\)个非负整数\(v, p\)（其中\(v\)表示该物品的价格(\(v \leq 10000\))，\(p\)表示该物品的重要度(\(1-5\))

Output

1个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值(\(<100000000\))。

首先声明,我真的不是在刷水题!只是为了打开下一个试炼场!

一个比较简单的背包问题。

我们设\(f[i]\)代表体积为\(i\)的时候的最大价值.

做法与\(01\)背包相同.不过将转移方程改一下即可.

妥妥的切掉

代码

#include<cstdio>

#include<cctype>

#include<iostream>

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int f[30008],ans,n,m;

int main()

{

	in(n);in(m);

	for(R int i=1,v,p;i<=m;i++)

	{

		in(v),in(p);

		for(R int j=n;j>=v;j--)

		{

			f[j]=max(f[j],f[j-v]+v*p);

			ans=max(ans,f[j]);

		}

	}

	printf("%d",ans);

}