二维背包问题，我是觉得这个题目数据比较水，虽然它最后说了怪可以无限个，但是它却只能最多杀s个，也就是所有品种的怪最多为s个，那么就是二维完全背包的问题了.......同时，它没有说一定要杀s只怪，所以在初始化全部赋值为0即可.......
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int dp[105][105],t[105][2];
int main()
{
int n,m,k,s;
while(scanf("%d %d %d %d",&n,&m,&k,&s)>0)
{
for(int i=1;i<=k;i++)
scanf("%d %d",&t[i][0],&t[i][1]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=k;i++)
{
for(int j=0;j<=s;j++)
{
for(int kk=0;kk<=m;kk++)
{
if(j>0&&kk>=t[i][1]&&dp[j-1][kk-t[i][1]]+t[i][0]>dp[j][kk])
{
dp[j][kk]=dp[j-1][kk-t[i][1]]+t[i][0];
//printf("%d\n",dp[j][kk]);
}
}
}
}
//printf("%d\n",dp[s][m]);
if(dp[s][m]<n)
printf("-1\n");
else
{
int maxn=10000000,x,y;
for(int i=0;i<=s;i++)
for(int j=0;j<=m;j++)
if(n<=dp[i][j]&&j<maxn)
maxn=j;
printf("%d\n",m-maxn);
}
}
return 0;
}