二维费用背包，第一个消费是忍耐值，第二个消费是杀怪数目。dp[i][j]表示杀了i个怪时剩余j的忍耐度。这个题目整个是二维背包套用完全背包的类型。比较有代表性。注释在代码里面
#include<iostream>
using namespace std;
int dp[105][105];
int v[105],cost[105];
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int main()
{
int n,m,k,s,i,j,p,flag,ok;
while(cin>>n>>m>>k>>s)
{
for(i=1;i<=k;i++)
cin>>v[i]>>cost[i];
memset(dp,0,sizeof(dp));
flag=0;
for(i=1;i<=k;i++)//怪物的种类
for(j=1;j<=s;j++)//刷怪数目，模拟完全背包
for(p=0;p<=m-cost[i];p++)//剩余的忍耐度。
{
dp[j][p]=maxi(dp[j][p],dp[j-1][p+cost[i]]+v[i]);
}
ok=-1;
//遍历一遍查找忍耐度最大的值。
for(i=m;i>=0;i--)
{
for(j=0;j<=s;j++)
if(dp[j][i]>=n)
{
flag=1;
if(i>ok)
ok=i;
}
}
if(flag==0)
cout<<"-1"<<endl;
else cout<<ok<<endl;
}
return 0;
}