二維完全背包,第二層跟第三層的要順序循環(huán);(0-1背包逆序循環(huán));狀態(tài)可理解為,在背包屬性為 {m(忍耐度), s(殺怪個(gè)數(shù))} 里最多能得到的經(jīng)驗(yàn)值,之前的背包犧牲體積,這個(gè)背包犧牲忍耐度跟個(gè)數(shù)

       狀態(tài)轉(zhuǎn)移方程為:  dp[i][j]=max ( dp[i][j],dp[ i-cost[k] ]+w[i]]:消耗i忍耐力殺j個(gè)怪獲得的經(jīng)驗(yàn)值

FATE

10 10 1 101 110 10 1 91 19 10 2 101 12 2 Sample Output
0-11 AuthorXhd
#include<iostream>using namespace std;int main(){	//0-1背包問題背包為 忍耐度  cost 怪消耗的忍耐力 w為得到的經(jīng)驗(yàn)值   int r,jin,n,maxn;   while(cin>>jin>>r>>n>>maxn)   {   	 int cost[205],w[205],i,j,k,x,y;   	 int dp[205][205];//dp[i][j]=t代表消耗i忍耐力殺j個(gè)怪獲得的經(jīng)驗(yàn)值    	 for(i=0;i<205;i++)   	   for(j=0;j<205;j++)   	   dp[i][j]=0;	 for(i=0;i<n;i++)   	    cin>>w[i]>>cost[i];   	 for(i=0;i<n;i++)//怪的種類   	    for(j=cost[i];j<=r;j++)//耐力		   for(k=1;k<=maxn;k++) //怪的個(gè)數(shù) 		   dp[j][k]=max(dp[j][k],dp[j-cost[i]][k-1]+w[i]);//注意為k-1 	int flag=0;	for(i=0;i<=r;i++)//注意掃的時(shí)候 外層循環(huán)為忍耐度,內(nèi)層循環(huán)為殺怪個(gè)數(shù),因?yàn)轭}目要求出剩余忍耐度最大,沒有約束殺怪個(gè)數(shù),一旦找到經(jīng)驗(yàn)加滿的即為最優(yōu)解;   {         if(flag==1) 	       break;	   for(j=0;j<=maxn;j++)	   {	   	  if(dp[i][j]>=jin)	   	  {	   	  	x=i; flag=1;break;	      }	   }	}	if(flag==0) 	  cout<<-1<<endl;	else	  cout<<r-x<<endl;	   }}