背包问题 | #点菜问题#

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

int main() {
    int C=0,N=0,w,v;
    while (cin >> C>> N) { // 注意 while 处理多个 case
        vector<vector<int>> arr;
        for(int i=0;i<N;i++){
            cin>>w>>v;
            arr.push_back({w,v});
        }
        vector<vector<int>> dp((C+1),vector<int>((N+1),0));
        for(int i=1;i<=C;i++){
            for(int j=1;j<=N;j++){
                if(i<arr[j-1][0]) 
                    dp[i][j]=dp[i][j-1];
                else{
                    dp[i][j]=max(arr[j-1][1]+dp[i-arr[j-1][0]][j-1],dp[i][j-1]);
                }
            }
        }
        cout<<dp[C][N]<<endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")