经典的01背包:这里体积为每个物品的价格,价值为价格*重要程度,做一遍01背包即可
#include<iostream>
using namespace std;
const int N=30010;
int f[N];
int main(){
int n,m;
cin>>m>>n;
for(int i=0;i<n;i++){
int v,w;
cin>>v>>w;
w=v*w;
for(int j=m;j>=v;j--){
f[j]=max(f[j],f[j-v]+w);
}
}
cout<<f[m]<<endl;
return 0;
}