題目描述

眾所周知，由于木星引力的影響，世界各地的推進(jìn)發(fā)動機(jī)都需要進(jìn)行重啟?，F(xiàn)在你接到緊急任務(wù)，要去收集火石碎片，重啟西郵發(fā)動機(jī)?，F(xiàn)在火石碎片已成為了稀缺資源，獲得火石碎片需要錢或者需要一定的積分?；鹗槠写笥行?#xff0c;越大的碎片能量越大，火石碎片的能量越大，重啟的發(fā)動機(jī)的推力也就越強(qiáng)。但是，不只有我們在努力呀，隔壁的師大和政法也都在收集碎片，爭取重啟師大發(fā)動機(jī)和政法發(fā)動機(jī)，哪個高校重啟的發(fā)動機(jī)推力最大，就能代表長安區(qū)大學(xué)城為世界做出貢獻(xiàn)，從而在史書上留下濃墨重彩的一筆。
現(xiàn)在你有v1塊錢，v2積分，能免費(fèi)(免積分)收集k個火石碎片，現(xiàn)在總共有n個火石碎片，每個碎片需要的錢a或者積分b，碎片的能量為val。我們希望收集火石碎片，使能量的總和盡可能大，問你skyer_hxx最多可以拿到能量總和的最大值是多少？

輸入

輸入包含多組測試用例。
每組數(shù)據(jù)的第一行是四個整數(shù)n，v1，v2，k；
然后是n行，每行三個整數(shù)a，b，val，分別表示每個碎片的價錢，兌換所需積分，所含能量。
1≤n≤100
0≤v1,v2≤100
0≤k≤5
0≤a,b,val≤100

輸出

對于每組數(shù)據(jù)，輸出能得到的最大能量值。?

樣例輸入

4 5 2 1 2 2 4 4 5 1 4 2 4 2 2 5

樣例輸出

14

提示

只要錢或者積分滿足購買一個碎片的要求，那么就可以買下這個碎片。?

　　可以看出這是個多條件的背包問題，但處理方法跟一維差不多，現(xiàn)在兩個條件就開2維，問題就是在于還可以免費(fèi)拿k個，一開始想當(dāng)然的以為就是那價值最大的那k個，其實(shí)不然，也可能的是價值小，但是條件很大的，所以還得再開個第三維。

　　也就是dp[i][j][k]表示的是有i塊錢j積分免費(fèi)拿k個的情況下能得到的最大價值。

1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int N=118; 5 struct Node{ 6 int a,b,val; 7 }w[N]; 8 int dp[N][N][10]; 9 int main() 10 { 11 int n,v1,v2,kk; 12 while(~scanf("%d%d%d%d",&n,&v1,&v2,&kk)){ 13 for(int i=0;i<n;i++) 14 scanf("%d%d%d",&w[i].a,&w[i].b,&w[i].val); 15 for(int i=0;i<=v1;i++) 16 for(int j=0;j<=v2;j++) 17 for(int k=0;k<=kk;k++) 18 dp[i][j][k]=0; 19 for(int i=0;i<n;i++) 20 for(int l=kk;l>=0;l--) 21 for(int j=v1;j>=0;j--) 22 for(int k=v2;k>=0;k--){ 23 if(l>=1) 24 dp[j][k][l]=max(dp[j][k][l],dp[j][k][l-1]+w[i].val); 25 if(j>=w[i].a) 26 dp[j][k][l]=max(dp[j][k][l],dp[j-w[i].a][k][l]+w[i].val); 27 if(k>=w[i].b) 28 dp[j][k][l]=max(dp[j][k][l],dp[j][k-w[i].b][l]+w[i].val); 29 } 30 printf("%d\n",dp[v1][v2][kk]); 31 } 32 return 0; 33 } 多條件呀

?

轉(zhuǎn)載于:https://www.cnblogs.com/LMCC1108/p/11115176.html

總結(jié)

以上是生活随笔為你收集整理的第四届西安邮电大学acm-icpc校赛 流浪西邮之寻找火石碎片 多体积条件背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。