首页 > 试题广场 >

点菜问题

[编程题]点菜问题

热度指数：12755 时间限制：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

算法知识视频讲解

吴明示

发表于 2022-03-21 21:22:06

#include <cstdio> #include <iostream> #include <cstring> using namespace std; //01背包问题求解实现中最难最绕的地方：二维数组的思想用一维数组表达 //思考：dp[i][j]表示把展开全文

yyer

发表于 2023-01-02 09:09:24

#include <iostream> using namespace std; int dp[101][1001]; int main() { int n,c; while(cin >> c >> n){ for(int i = 0; i 展开全文

在考古的小鱼干很有气魄

发表于 2023-03-09 09:38:01

#include <bits/stdc++.h> #define MAX 1000 using namespace std; int main() { int dp[MAX], w[MAX], v[MAX]; int C, N; //C报销额度，N数量 whi 展开全文

Starfirz

发表于 2021-03-23 16:01:45

#include <iostream> #include <vector> using namespace std; int main(){ int n, c; while(cin >> c >> n){ int i 展开全文

笑川不吃香菜

发表于 2024-03-07 09:36:17

#include <bits/stdc++.h> using namespace std; int main() { int totalWeight, type; while (cin >> totalWeight >> type) { 展开全文

yigu2468

发表于 2024-03-08 19:35:28

#include <iostream> using namespace std; const int MAXN = 101; const int MAXP = 1001; // dp数组在主函数外定义，元素自动初始化0 int dp[MAXN][MAXP], v[MAXN], w[ 展开全文

asksl

发表于 2022-08-30 21:40:52

0-1背包问题； #include<iostream> #include<cstdio> using namespace std; const int maxm=1001; const int maxn=101 展开全文

lll宁

发表于 2022-03-18 21:45:03

#include<iostream> using namespace std; const int MAXN=1000+10; int weight[MAXN];//钱数 int value[MAXN];//评价 int dp[MAXN]; int main(){ &nbs 展开全文

606060

发表于 2023-03-29 23:00:37

#include <iostream> #include <iterator> using namespace std; struct f { int m;//每道菜的价格 int y;//每道菜的营养 }; int main() { int C, 展开全文

philos

发表于 2021-03-02 13:23:11

思路很经典的 0-1 背包问题，不太熟悉的可以去看一下背包九讲，报销经费的总额就是背包的容量，其实背包问题也是动态规划，我们用 dp[i][j] 表示前 i 种菜报销经费为 j 时的最大总评价分数，那么最后结果就是dp[N][C] 我们再来看看状态转移方程怎么写，对于第 i 种菜，我们可以选择也可展开全文

问题信息

动态规划

难度：

65条回答 162收藏 9020浏览

通过挑战的用户

查看代码

牛客43854...

2023-03-12 17:21:14
张泽耀1

2023-03-08 20:13:47
你的生活我的梦a

2023-03-08 10:27:19
monster丶梁菜

2023-03-07 09:44:05
xiaojunjun

2023-03-06 16:40:18

点菜问题

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题