1152_点菜问题

2019-11-11 06:21:58

字体：大中小

来源：转载

供稿：网友

// 1152_点菜问题.cpp : 定义控制台应用程序的入口点。//题目1152：点菜问题//时间限制：1 秒内存限制：32 兆特殊判题：否提交：1182解决：609//题目描述：// 北大网络实验室经常有活动需要叫外买，但是每次叫外买的报销经费的总额最大为C元，有N种菜可以点，经过长时间的点菜，网络实验室对于每种菜i都有一个量化的评价分数（表示这个菜可口程度），为Vi，每种菜的价格为Pi, 问如何选择各种菜，使得在报销额度范围内能使点到的菜的总评价分数最大。// 注意：由于需要营养多样化，每种菜只能点一次。//输入：// 输入的第一行有两个整数C（1 <= C <= 1000）和N（1 <= N <= 100），C代表总共能够报销的额度，N>代表能点菜的数目。接下来的N行每行包括两个在1到100之间（包括1和100）的的整数，分别表示菜的>价格和菜的评价分数。//输出：// 输出只包括一行，这一行只包含一个整数，表示在报销额度范围内，所点的菜得到的最大评价分数。//样例输入：//90 4//20 25//30 20//40 50//10 18//40 2//25 30//10 8//样例输出：//95//38//来源：//2010年北京大学计算机研究生机试真题#include "stdafx.h"#include "stdio.h"#include "algorithm"#include "iostream"#include "string.h"using namespace std;int PRice[1010],score[110];int c[110][1010];int main(){ int C,N; while(cin>>C>>N){ memset(c,0,sizeof(c)); for(int i = 1;i<=N;i++) cin>>price[i]>>score[i]; for(int i = 1;i<=N;i++){ for(int j = 1;j<=C;j++){ if(j>=price[i]) c[i][j] = max(c[i-1][j],c[i-1][j-price[i]]+score[i]); else c[i][j] = c[i-1][j]; } } cout<<c[N][C]<<endl; } return 0;}/*一维数组优化：#include<iostream> #include<string.h> #include<algorithm> using namespace std; int a[1002],b[102],c[102]; int main() { int n,m,i,j; while(cin>>n>>m) { memset(a,0,sizeof(a)); for(i=1;i<=m;i++) cin>>b[i]>>c[i]; for(i=1;i<=m;i++) for(j=n;j>=b[i];j--) //逆序，j只要循环到等于b[i]的值就好 a[j]=max(a[j],a[j-b[i]]+c[i]); cout<<a[n]<<endl; } return 0; } */

上一篇：汉字统计

下一篇：hdu 2048 错排公式神、上帝以及老天爷

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注