开心的金明

转换成0-1背包问题即可

#include<iostream>
#include<cstring>
#include<algorithm>
#define N 30
#define M 30010

using namespace std;

int n,m;
int f[M];

int main()
{
    cin >> m >> n;
    for(int i = 1;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;
}