1152_點菜問題

2019-11-11 05:49:13

字體：大中小

供稿：網(wǎng)友

// 1152_點菜問題.cpp : 定義控制臺應(yīng)用程序的入口點。//題目1152：點菜問題//時間限制：1 秒內(nèi)存限制：32 兆特殊判題：否提交：1182解決：609//題目描述：// 北大網(wǎng)絡(luò)實驗室經(jīng)常有活動需要叫外買，但是每次叫外買的報銷經(jīng)費的總額最大為C元，有N種菜可以點，經(jīng)過長時間的點菜，網(wǎng)絡(luò)實驗室對于每種菜i都有一個量化的評價分?jǐn)?shù)（表示這個菜可口程度），為Vi，每種菜的價格為Pi, 問如何選擇各種菜，使得在報銷額度范圍內(nèi)能使點到的菜的總評價分?jǐn)?shù)最大。// 注意：由于需要營養(yǎng)多樣化，每種菜只能點一次。//輸入：// 輸入的第一行有兩個整數(shù)C（1 <= C <= 1000）和N（1 <= N <= 100），C代表總共能夠報銷的額度，N>代表能點菜的數(shù)目。接下來的N行每行包括兩個在1到100之間（包括1和100）的的整數(shù)，分別表示菜的>價格和菜的評價分?jǐn)?shù)。//輸出：// 輸出只包括一行，這一行只包含一個整數(shù)，表示在報銷額度范圍內(nèi)，所點的菜得到的最大評價分?jǐn)?shù)。//樣例輸入：//90 4//20 25//30 20//40 50//10 18//40 2//25 30//10 8//樣例輸出：//95//38//來源：//2010年北京大學(xué)計算機研究生機試真題#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;}/*一維數(shù)組優(yōu)化：#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只要循環(huán)到等于b[i]的值就好 a[j]=max(a[j],a[j-b[i]]+c[i]); cout<<a[n]<<endl; } return 0; } */

上一篇：VIM入門

下一篇：344. Reverse String