题解 | #点菜问题#

#include <iostream>
#include <iterator>
using namespace std;

struct f
{
    int m;//每道菜的价格
    int y;//每道菜的营养
};

int main() {
    int C,N;//C:钱 N：个数
    while(cin>>C>>N)
    {
        f a[N];
        for(int i=0;i<N;++i)
        {
            cin>>a[i].m>>a[i].y;
        }
        int k[N][C+1];

        for(int i=0;i<N;++i)
        {
            for(int j=0;j<=C;++j)
            {
                if(j < a[i].m)
                {
                    if(i-1>=0)
                    {
                        k[i][j] = k[i-1][j];
                    }
                    else 
                    {
                        k[i][j] = 0;
                    }
                }
                else 
                {
                    if(i-1>=0)
                    {
                        if(a[i].y+k[i-1][j-a[i].m]>k[i-1][j])
                        {
                            k[i][j] = a[i].y+k[i-1][j-a[i].m];
                        }
                        else 
                        {
                            k[i][j] = k[i-1][j];
                        }
                    }
                    else 
                    {
                        k[i][j] = a[i].y;
                    }
                }
            }
        }
        cout<<k[N-1][C]<<endl;
    }
}