wyh12 2019-10-30 03:39:26
点我顶贴
收藏
删除
#include<iostream>
using namespace std;
inline int max(int a,int b){
return a>b?a:b;
}
int w[30],v[30],f[5000000];
int main()
{
int m,n;
cin>>m>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i]>>v[i];
v[i]*=w[i]; //唯一要注意的地方 价值存储时要注意
}
for(int i=1;i<=n;i++)//常规的01
for(int j=m;j>=w[i];j--)
f[j]=max(f[j],f[j-w[i]]+v[i]);
cout<<f[m]<<endl;
return 0;
}
/*
一道神奇的动态规划(背包)
思维难,做法简单
*/