liyangjida 2018-06-18 22:10:52
点我顶贴
收藏
删除
/*
dp[n][j]=0;
dp[i][j]=dp[i+1][j](j < v[i]);
dp[i][j]=max(dp[i+1][j],dp[i+1][j-v[i]] + v[i]*w[i]);
*/
#include<iostream>
#include<algorithm>
using namespace std;
int N;
int m;
int v[25];
int w[25];
int dp[30000];
int main()
{
cin >> N >> m;
for (int i = 0; i < m; ++i)
cin >> v[i] >> w[i];
for (int i = 0; i < m; ++i)
for (int j = N;j >= v[i]; --j)
dp[j] = max(dp[j], dp[j - v[i]] + v[i] * w[i]);
cout << dp[N] << endl;
return 0;
}