HDU2159FATE（二维费用背包）

解题思路：第二题二维费用背包了，有些许的理解，

状态设计：dp[z][j]表示杀z个怪花费不超过j的情况下得到的最大经验值

状态转移方程：dp[z][j]=max(dp[z][j],dp[z-1][j-cost[i]]+value[i])

相当于多一维限定杀敌数的花费，而你要多杀一个人一定是从你杀的z-1个人的状态推导过来的。j的那个循环控制到底是01背包还是完全背包

AC代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int max(int a,int b)
{
	return a>b?a:b;
}

const int inf=0x3f3f3f3f;

int dp[110][110],cost[110],value[110],n,m,k,s;

int main()
{
	int i,j,z,Min;
	while(~scanf("%d%d%d%d",&n,&m,&k,&s)) //n经验值 m忍耐度 k种类 s杀敌数
	{
		memset(dp,0,sizeof(dp));
		for(i=0;i<k;i++)
			scanf("%d%d",&value[i],&cost[i]); //value经验  cost忍耐度
		Min=inf;
		for(i=0;i<k;i++)
		{
			for(j=cost[i];j<=m;j++)
			{
				for(z=1;z<=s;z++)
				{
					dp[z][j]=max(dp[z][j],dp[z-1][j-cost[i]]+value[i]);
					if(dp[z][j]>=n && Min>j)
						Min=j;
				}
			}
		}
		if(Min==inf)
			printf("-1\n");
		else
			printf("%d\n",m-Min);
	}
	return 0;
}