題目描述

翰的奶牛玩游戲成癮！本來約翰是想把她們拖去電擊治療的，但是他發現奶牛們在玩游戲后生產 了更多的牛奶，也就支持它們了。 但是，奶牛在選擇游戲平臺上的分歧很大：有些奶牛想買 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 }

?

轉載于:https://www.cnblogs.com/Yuzao/p/6992342.html

總結

以上是生活随笔為你收集整理的【USACO】电子游戏 有条件的背包的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。