【正经题解】开心的金明

这题原本是一道基本的 01 背包 ， 动态规划 。
只需将价格与重要度提前算好 ， 再套模板即可 。

#include <iostream>

using namespace std;

int f[30][100000];
int w[10000];
int v[10000];

int main()
{
    int n,m;
    int i,j,k;
    cin>>m>>n;
    //提前相乘
    for(i=1;i<=n;i++)
    {
        cin>>w[i]>>v[i];
        v[i]*=w[i];
    }
    for(int i=1;i<=n;i++)
    {
        //01背包最关键的位置,为防止反复加同一物品，需要倒着搜，这也是01背包与完全背包的不同之处
        for(int c=0;c<=m;c++)
        {
            f[i][c]=f[i-1][c];
            if(c>=w[i])
            f[i][c]=max(f[i][c],f[i-1][c-w[i]]+v[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}