讨论 / c++ AC100
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;

}

查看更多回复
提交回复