题解 | #点菜问题#

//经典0-1背包，采用动态规划的做法
#include "stdio.h"
#include "algorithm"
using namespace std;

int main(){
    int C,N;
    int price[110];
    int credit[110];
    int dp[110][1010];
    while (scanf("%d%d",&C,&N)!=EOF){
        for (int i = 1; i <= N; ++i) {
            scanf("%d%d",price+i,credit+i);
        }
        for (int i = 0; i <= N; ++i) {//i为菜品的下标
            for (int j = 0; j <= C; ++j) {//j为weight(剩下的钱)
                if (i == 0 || j == 0){//没有菜品可选或没钱了
                    dp[i][j] = 0;
                    continue;
                }
                if (j < price[i])
                    dp[i][j] = dp[i-1][j];//菜太贵，超过了weight，没法买
                else
                    dp[i][j] = max(dp[i-1][j-price[i]]+credit[i],dp[i-1][j]);//买此菜品与不买此
                                                                             //菜品中选择评分高的
            }
        }
        printf("%d\n",dp[N][C]);
    }
}