考察点

01背包

C++ 代码

#include <iostream>

using namespace std;

const int N=30010,M=35;

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

int main(){
    cin>>m>>n;

    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
     for(int j=m;j>=v[i];j--)
      f[j]=max(f[j],f[j-v[i]]+v[i]*w[i]);     

     cout<<f[m];

    return 0;
}