http://acm.hdu.edu.cn/showproblem.php?pid=2159

題意：

　　給出的n , m , k ,s 分別代表還需n經(jīng)驗(yàn)升級(jí)、還有m耐久度、下面有k組數(shù)據(jù)、最多能殺s只怪，下面k組的a和b分別

代表殺一只這種怪要消耗b耐久度獲得a經(jīng)驗(yàn)，讓你計(jì)算出在耐久度和殺怪?jǐn)?shù)范圍內(nèi)能不能獲得題目給出的經(jīng)驗(yàn)。

?

坑爹：

　　一開(kāi)始我想的時(shí)候以為是多重背包的問(wèn)題，我以為是每種怪都能殺s次，其實(shí)是總共只能殺s只怪，所以不能用多重背包做。

?

解法：

　　二維費(fèi)用的背包問(wèn)題，用一個(gè)DP的二維數(shù)組，DP[ i?][ j?]? i 代表殺怪?jǐn)?shù) ， j 代表耐久度 。因?yàn)槊總€(gè)怪可以打多次，所以

Pack函數(shù)里的循環(huán)是順序的。

?

View Code 1 #include<iostream> 2 using namespace std; 3 4 const int maxn = 100 + 10; 5 int DP[maxn][maxn]; 6 int n; 7 int m; 8 int k; 9 int s; 10 11 int max(int a,int b) 12 { 13 return a > b ? a : b; 14 } 15 16 void Pack(int cost,int weight) 17 { 18 int i; 19 int j; 20 for(i=1; i<=s; i++) 21 { 22 for(j=cost; j<=m; j++) 23 { 24 DP[i][j] = max(DP[i][j] , DP[i-1][j-cost]+weight); 25 } 26 } 27 } 28 29 int main() 30 { 31 while(cin>>n>>m>>k>>s) 32 { 33 int i; 34 int worth[maxn]; 35 int heavy[maxn]; 36 memset(DP,0,sizeof(DP)); 37 for(i=1; i<=k; i++) 38 { 39 cin>>worth[i]>>heavy[i]; 40 } 41 for(i=1; i<=k; i++) 42 { 43 Pack(heavy[i],worth[i]); 44 } 45 46 int flag = 0; 47 for(i=1; i<=m; i++) 48 { 49 if(DP[s][i]>=n) 50 { 51 cout<<m-i<<endl; 52 flag = 1; 53 break; 54 } 55 } 56 if(!flag) 57 { 58 cout<<-1<<endl; 59 } 60 } 61 return 0; 62 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/pcpcpc/archive/2012/09/13/2682989.html

總結(jié)

以上是生活随笔為你收集整理的HDU 2159 FATE 动态规划二维费用的背包问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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