首页 > 试题广场 >

点菜问题

[编程题]点菜问题

热度指数：12847 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

北大网络实验室经常有活动需要叫外卖，但是每次叫外卖的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。注意：由于需要营养多样化，每种菜只能点一次。

输入描述:

    输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。

输出描述:

    输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。

示例1

输入

输出

95
38

算法知识视频讲解

顶呱呱的火龙果很不想上网课

#include <stdio.h>
struct goods{
    int price;
    int value;
};
int main(){
    int dp[101][1001] = {0};
    int c, n;
    struct goods a[101];
    scanf("%d%d", &c, &n);
    for (int i = 1; i <= n; i ++) {
        scanf("%d%d", &a[i].price, &a[i].value);
    }
    for(int i = 1;i <= n; i ++){
        for (int j = 1; j <= c; j ++) {
            int t1 = dp[i-1][j];
            int t2 = 0;
            if (j-a[i].price>=0) {
                t2 = dp[i-1][j-a[i].price]+a[i].value;
            }
            dp[i][j] = t1>t2?t1:t2;
        }
    }
    printf("%d", dp[n][c]);
    return 0;
}

发表于 2023-03-06 15:08:59 回复(0)