题目描述
翰的奶牛玩游戏成瘾！本来约翰是想把她们拖去电击治疗的，但是他发现奶牛们在玩游戏后生产
了更多的牛奶，也就支持它们了。
但是，奶牛在选择游戏平台上的分歧很大：有些奶牛想买 Xbox 360 来跑《光晕 3》；有的奶牛想
要任天堂 Wii 来跑《明星大乱斗 X》；还有奶牛想要在 PlayStation 3 上玩《潜龙谍影 4》。约翰只有
V 元钱，不够多，要做一些取舍才行。
已知市面上有 K 种游戏平台，如果想玩第 i 种平台的游戏，必须先买一台该平台的游戏机，价
格为 C i 。第 i 种平台上有 S i 种游戏，其中第 j 个游戏的价格为 P i,j ，奶牛玩过这个游戏后的产出为
E i,j 。如果想玩同一平台上的多个游戏，只要买一台游戏机就够了。请帮助约翰选择买哪些游戏机和
游戏，才能使奶牛的产奶效益之和最大？注意同一个游戏买两次是不会产生双倍效益产生的。
输入
• 第一行：两个整数 K 和 V ，1 ≤ K ≤ 50,1 ≤ V ≤ 10 6
• 第二行到第 K + 1 行：第 i + 1 行首先有两个整数 C i 和 S i ，1 ≤ C i ≤ 10 6 ,1 ≤ S i ≤ 10，其次
有 S i 对整数 P i,j 和 E i,j ，1 ≤ P i,j ≤ 10 6 ,1 ≤ E i,j ≤ 10 6
输出
• 单个整数：表示可以得到的最大产出之和
样例输入
3 800 300 2 30 50 25 80 600 1 50 130 400 3 40 70 30 40 35 60
样例输出
210
提示
购买第一种游戏平台上的第二个游戏，以及
第三种游戏平台上的第一个和第三个游戏，恰好
花去 300 + 25 + 400 + 40 + 35 = 800 元，产出为
80 + 70 + 60 = 210
题解：
捆绑背包加强版，分选该平台和不选两种情况 于是我们设F[i][j]为前i个平台花j元的最大产出
我们假设买了该平台，设nd为买该平台的钱 那么F[i][j]=F[i-1][j-nd] 先转移过来
然后再用所有的游戏进行01背包 然后枚举需要限制.
背包完之后拿F[i][j]和F[i][j-1]比较，表示选不选该平台
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=55,MAXN=1000005; 7 int F[N][MAXN]; 8 int gi(){ 9 int str=0;char ch=getchar(); 10 while(ch>'9'||ch<'0')ch=getchar(); 11 while(ch>='0' && ch<='9')str=str*10+ch-48,ch=getchar(); 12 return str; 13 } 14 int main() 15 { 16 int n=gi(),m=gi(),nd,num=0,x,y; 17 for(int i=1;i<=n;i++) 18 { 19 nd=gi();num=gi(); 20 for(int j=nd;j<=m;j++)F[i][j]=F[i-1][j-nd]; 21 for(int j=1;j<=num;j++) 22 { 23 x=gi();y=gi(); 24 for(int k=m;k>=x+nd;k--) 25 { 26 F[i][k]=max(F[i][k-x]+y,F[i][k]); 27 } 28 } 29 for(int j=0;j<=m;j++)F[i][j]=max(F[i][j],F[i-1][j]); 30 } 31 printf("%d",F[n][m]); 32 return 0; 33 }