二维完全背包,第二层跟第三层的要顺序循环;(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;	   }}