題目描述：
大家都知道在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
算法分析
這道題主要的屬於背包問題，用動態規劃解決，需要注意的是兩點。
1. 我們把合成的裝備看作單獨的一件裝備，計算合成裝備的價格（合成所需裝備價格之和），合成裝備的價值（合成所需裝備價值之和 加上 額外價值）。
[cpp]
for(int i = num_weapons;i<num_weapons+num_merge;i++){
int t=0;
std::cin>>t;
price[i]=0;
value[i]=0;
for(int j = 0;j<t;j++){
int id_weapon;
std::cin>>id_weapon;
price[i]+=price[id_weapon-1];
value[i]+=value[id_weapon-1];
}
int s = 0;
std::cin>>s;
value[i]+=s;
}
for(int i = num_weapons;i<num_weapons+num_merge;i++){
int t=0;
std::cin>>t;
price[i]=0;
value[i]=0;
for(int j = 0;j<t;j++){
int id_weapon;
std::cin>>id_weapon;
price[i]+=price[id_weapon-1];
value[i]+=value[id_weapon-1];
}
int s = 0;
std::cin>>s;
value[i]+=s;
} 2.這道題和其它背包問題不同的在於 裝備的數量並不是固定的，玩家可以重復購買多個同一種裝備，包括合成裝備，只要錢夠就行。所以在動態規劃更新dp的時候，就是從低到高更新。
[cpp]
for(int j = price[i];j<gold+1;j++){
maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
}
for(int j = price[i];j<gold+1;j++){
maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
} 參考題目1209：最小郵票數
普通背包問題
題目1364：v字仇殺隊
題目1462：兩船載物問題
題目1455：珍惜現在，感恩生活
題目1209：最小郵票數
題目1420：Jobdu MM分水果
項目安排類題目
題目1499：項目安排
題目1463：招聘會
題目1434：今年暑假不AC
資源無限求最大值的題目。
題目1494：Dota
源程序
[cpp]
/============================================================================
// Name : judo1494.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//02988825547
#include <iostream>
#include <cmath>
using namespace std;
void dota(int num_weapons,int num_merge,int gold){
int *price = new int[num_weapons+num_merge];
int *value = new int[num_weapons+num_merge];
int *maxvalue = new int[gold+1];
for(int i = 0;i<num_weapons;i++){
std::cin>>price[i]>>value[i];
}
for(int i = num_weapons;i<num_weapons+num_merge;i++){
int t=0;
std::cin>>t;
price[i]=0;
value[i]=0;
for(int j = 0;j<t;j++){
int id_weapon;
std::cin>>id_weapon;
price[i]+=price[id_weapon-1];
value[i]+=value[id_weapon-1];
}
int s = 0;
std::cin>>s;
value[i]+=s;
}
for(int i = 0;i<gold+1;i++){
maxvalue[i]=0;
}
for(int i = 0;i<num_weapons+num_merge;i++){
for(int j = price[i];j<gold+1;j++){
maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
}
}
std::cout<< maxvalue[gold]<<std::endl;
delete []price;
delete []value;
delete []maxvalue;
}
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
int n;
int m;
int g;
while(std::cin>>n>>m>>g){
dota(n,m,g);
}
return 0;
}
/**************************************************************
Problem: 1494
User: KES
Language: C++
Result: Accepted
Time:30 ms
Memory:1520 kb
****************************************************************/
//============================================================================
// Name : judo1494.cpp
// Author :
// Version :
// Copyright : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
//02988825547
#include <iostream>
#include <cmath>
using namespace std;
void dota(int num_weapons,int num_merge,int gold){
int *price = new int[num_weapons+num_merge];
int *value = new int[num_weapons+num_merge];
int *maxvalue = new int[gold+1];
for(int i = 0;i<num_weapons;i++){
std::cin>>price[i]>>value[i];
}
for(int i = num_weapons;i<num_weapons+num_merge;i++){
int t=0;
std::cin>>t;
price[i]=0;
value[i]=0;
for(int j = 0;j<t;j++){
int id_weapon;
std::cin>>id_weapon;
price[i]+=price[id_weapon-1];
value[i]+=value[id_weapon-1];
}
int s = 0;
std::cin>>s;
value[i]+=s;
}
for(int i = 0;i<gold+1;i++){
maxvalue[i]=0;
}
for(int i = 0;i<num_weapons+num_merge;i++){
for(int j = price[i];j<gold+1;j++){
maxvalue[j] = std::max(maxvalue[j],maxvalue[j-price[i]]+value[i]);
}
}
std::cout<< maxvalue[gold]<<std::endl;
delete []price;
delete []value;
delete []maxvalue;
}
int main() {
//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
int n;
int m;
int g;
while(std::cin>>n>>m>>g){
dota(n,m,g);
}
return 0;
}
/**************************************************************
Problem: 1494
User: KES
Language: C++
Result: Accepted
Time:30 ms
Memory:1520 kb
****************************************************************/
