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

       狀態轉移方程為:  dp[i][j]=max ( dp[i][j],dp[ i-cost[k] ]+w[i]]:消耗i忍耐力殺j個怪獲得的經驗值

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為得到的經驗值   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個怪獲得的經驗值    	 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++) //怪的個數 		   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++)//注意掃的時候 外層循環為忍耐度,內層循環為殺怪個數,因為題目要求出剩余忍耐度最大,沒有約束殺怪個數,一旦找到經驗加滿的即為最優解;   {         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;	   }}