二維背包，既有耐性度限制又有怪獸的個數的限制，每種怪獸是無限多個就說明是二維的無限背包。
代碼：
[cpp]
#include<iostream>
using namespace std;
int a[105],b[105],dp[105][105];
int main()
{
int n,m,k,s,i,j,l;
while( scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF){
for( i=0; i<k; i++)
scanf("%d%d",&a[i],&b[i]);
memset(dp,0,sizeof(dp));
for( i=0; i<k; i++)
for( j=b[i]; j<=m; j++)
for( l=1; l<=s; l++)
dp[j][l]=max(dp[j][l],dp[j-b[i]][l-1]+a[i]);
bool flag=false;
for( i=0; i<=m&&!flag; i++){
for( j=0; j<=s&&!flag; j++){
if( dp[i][j]>=n){
flag=true;
printf("%d\n",m-i);
}
}
}
if( !flag)
printf("-1\n");
}
return 0;
}
作者：aacm1992
