P1060 开心的金明

题目链接：P1060 开心的金明

01背包：

#include<iostream>

using namespace std;

const int M = 30010,N = 30;

/*
状态表示：f[i][j]表示前i个价格为j的最大价值 

状态转移：不选
			  f[i][j] = f[i - 1][j]; 
		  选
		  	  f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
		
初始化：f[0][0] = 0;

res = max(res,f[n][0~m]) 
*/

int n,m;
int f[M];
int v[N],w[N];
int res;

int main() {
	cin >> m >> n;
	for(int i = 1; i <= n; i ++ ){
		int a,b;  cin >> a >> b;
		v[i] = a;w[i] = a * b;
	}
	for(int i = 1; i <= n; i ++ ){
		for(int j = m; j >= v[i]; j -- ){
				f[j] = max(f[j],f[j - v[i]] + w[i]);
			}
		}
	cout<<f[m]<<endl; 						
	return 0;
}