Jobdu 1494：Dota - KingEasternSun的专栏 - 博客频道 - CSDN.NET

九度笔记之 1494：Dota - KingEasternSun的专栏 - 博客频道 - CSDN.NET

大家都知道在dota游戏中，装备是对于英雄来说十分重要的要素。
英雄们不仅可以购买单个的装备，甚至某些特定的装备组合能够合成更强的装备。
为了简化问题，我们将每个装备对于英雄的功能抽象为一个整数：价值。同时，如上所说，一些特定的装备可以用来合成更强的装备，玩家会因此获得除原装备价值外额外的价值。
给定玩家现有的金钱数，每个装备的价格和其对应的价值，以及装备合成的信息。输出，其能获得的最大价值数。
注意：每件装备只能参与合成一件合成装备（即原装备参与合成后得到合成后的新装备，原装备消失），除非一次购买多个该种装备。

输入：

输入包含多组测试数据，每组测试数据第一行为三个整数n，m，g(1<=n<=100),(0<=m<=100),(1<=g<=1000)。
分别表示存在的装备总数n，存在的装备合成关系数m，和英雄所有的金钱g。
接下去n行，每行两个整数（p，v）（1<=p<=100,1<=v<=100）分别表示该件装备的价格p，和其自身的价值v。
每组测试数据的最后为m行数据，每行由两部分组成。开头一个整数t(1<=t<=n)，表示该组合成关系中需要t件装备，下去紧跟t件装备编号（按照装备在输入中的顺序从1到n编号），表示参与合成该装备的装备编号，最后一个数s（1<=s<=1000），代表这t件物品合成道具后获得的额外价值。

输出：

对于每组测试数据，输出一个整数，代表英雄可以获得的最大价值。

样例输入：

3 1 100
100 20
50 9
50 9
2 2 3 1
3 1 100
100 20
50 9
50 9
2 2 3 3


样例输出：
20
21

http://blog.csdn.net/u013027996/article/details/26989653
装备是没有购买上限的, 这就简单多了
2. 假如给定的装备只能取一件, 装备之间又能合成新装备, 那么这道题就难了
完全背包，内层循环是从小到大。注意合成值也要单独得到花费和价值。

1.     public static void main(String[] args) throws Exception {  
2.         StreamTokenizer st = new StreamTokenizer(new BufferedReader(  
3.                 new InputStreamReader(System.in)));  
4.         while (st.nextToken() != StreamTokenizer.TT_EOF) {  
5.             int n = (int) st.nval;  
6.             st.nextToken();  
7.             int m = (int) st.nval;  
8.             st.nextToken();  
9.             int g = (int) st.nval;  
10.             int size = n + 1 + m;  
11.             int p[] = new int[size];  
12.             int v[] = new int[size];  
13.             for (int i = 1; i < n + 1; i++) {  
14.                 st.nextToken();  
15.                 p[i] = (int) st.nval;  
16.                 st.nextToken();  
17.                 v[i] = (int) st.nval;  
18.             }  
19.             for (int i = n + 1; i < size; i++) {  
20.                 st.nextToken();  
21.                 int t = (int) st.nval;  
22.                 for (int j = 1; j < t + 1; j++) {  
23.                     st.nextToken();  
24.                     int seq = (int) st.nval;  
25.                     p[i] += p[seq];  
26.                     v[i] += v[seq];  
27.                 }  
28.                 st.nextToken();  
29.                 int s = (int) st.nval;  
30.                 v[i] += s;  
31.             }  
32.             int dp[] = new int[g + 1];  
33.             for (int i = 1; i < size; i++) {  
34.                 for (int j = p[i]; j <= g; j++) {  
35.                     dp[j] = Math.max(dp[j], dp[j - p[i]] + v[i]);  
36.                 }  
37.             }  
38.             System.out.println(dp[g]);  
39.         }  
40.     }  
41. }  

http://blog.csdn.net/wdy_yx/article/details/9815631
我们把合成的装备看作单独的一件装备，计算合成装备的价格（合成所需装备价格之和），合成装备的价值（合成所需装备价值之和 加上 额外价值）

1. for(int i = num_weapons;i<num_weapons+num_merge;i++){  
2.     int t=0;  
3.     std::cin>>t;  
4.     price[i]=0;  
5.     value[i]=0;  
6.     for(int j = 0;j<t;j++){  
7.         int id_weapon;  
8.         std::cin>>id_weapon;  
9.         price[i]+=price[id_weapon-1];  
10.         value[i]+=value[id_weapon-1];  
11.     }  
12.     int s = 0;  
13.     std::cin>>s;  
14.     value[i]+=s;  
15. }  

2.这道题和其它背包问题不同的在于 装备的数量并不是固定的，玩家可以重复购买多个同一种装备，包括合成装备，只要钱够就行。所以在动态规划更新dp的时候，就是从低到高更新。

1. void dota(int num_weapons,int num_merge,int gold){  
2.     int *price = new int[num_weapons+num_merge];  
3.     int *value = new int[num_weapons+num_merge];  
4.     int *maxvalue = new int[gold+1];  
5.     for(int i = 0;i<num_weapons;i++){  
6.         std::cin>>price[i]>>value[i];  
7.     }  
8.     for(int i = num_weapons;i<num_weapons+num_merge;i++){  
9.         int t=0;  
10.         std::cin>>t;  
11.         price[i]=0;  
12.         value[i]=0;  
13.         for(int j = 0;j<t;j++){  
14.             int id_weapon;  
15.             std::cin>>id_weapon;  
16.             price[i]+=price[id_weapon-1];  
17.             value[i]+=value[id_weapon-1];  
18.         }  
19.         int s = 0;  
20.         std::cin>>s;  
21.         value[i]+=s;  
22.     }  
23.    
24.     for(int i = 0;i<gold+1;i++){  
25.         maxvalue[i]=0;  
26.     }  
27.     for(int i = 0;i<num_weapons+num_merge;i++){  
28.         for(int j = price[i];j<gold+1;j++){  
29.             maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);  
30.         }  
31.     }  
32.     std::cout<< maxvalue[gold]<<std::endl;  
33.     delete []price;  
34.     delete []value;  
35.     delete []maxvalue;  
36.    
37. }  

Read full article from 九度笔记之 1494：Dota - KingEasternSun的专栏 - 博客频道 - CSDN.NET