使用C++破解小飞侠游园方案

题目描述

      小飞侠星期天会邀他的灵儿妹妹到公园去玩。公园里有很多娱乐项目，可并不是每一项他们都喜欢，所以他们对每一项都进行了“喜欢度”的评分。因为小飞侠也是一个了不起的角色，所以他一定会选择在有限时间内的最好的方案。现在要你做的就是找出在规定时间内他们选择哪几项不同的活动可以使其“喜欢度”之和达到最大。

输入

第一行一个正整数N（1<=N<=100）表示总共的娱乐项目数。

第二行一个正整数表示规定的时间t（0<t<1000）。

下面有N行，其中第i+2行有两个正整数fi（0<=fi<=100）和ti（0<ti<=100），分别表示对项目i的“喜欢度”和它所耗费的时间。

输出

       第一行输出最大的“喜欢度”之和。

样例输入 

3
5
1 2
5 5
4 3

样例输出 

5 

代码

 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main(){
 5     int N;
 6     int W;
 7     int w[30]={0};
 8     int v[30]={0};
 9     int k,C;
10     int p;
11     int B[30][200] = {0}; 
12     cin>>W>>N;
13     for(p=1;p<N+1;p++){
14         cin>>w[p] >>v[p];
15     }
16         for(k=1;k<N+1;k++){
17             for(C = 1;C < W+1;C++){
18                 if(w[k] > C){
19                     B[k][C] = B[k-1][C];
20                 }
21                 else{
22                     int value1 = B[k-1][C-w[k]] + v[k];
23                     int value2 = B[k-1][C];
24                     if(value1 > value2){
25                         B[k][C] = value1;
26                     }
27                     else{
28                         B[k][C] = value2;
29                     }
30                 }
31             }
32         }    
33         cout<<B[N][W ]<<endl;
34     return 0;
35 }