题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2159
解题报告：这题实际上是一个二维的背包问题，也可以由01背包扩展而来，01背包用一维数组，可想而知二维背包应该二维数组，然后每一维表示它的一种不同的需要付出的代价，普通的二维背包的递推公式是dp[j][k] = max(dp[j][k],w[j-v[i][k-n[i]] + w[i]);，要注意的是这是一般的二维背包的递推公式，但是在这题中有一点小小的变化，就是
怪的个数有无限个，也就是说每件物品都可以取无限次，所以还要再加上一层循环，这个应该简单。具体见代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int a,b,exp;
node()
{
b = ;
}
}guai[];
int E[][],flag[]; int main()
{
int n,m,k,s;
while(scanf("%d%d%d%d",&n,&m,&k,&s)!=EOF)
{
for(int i = ;i < k;++i)
scanf("%d%d",&guai[i].exp,&guai[i].a);
memset(E,,sizeof(E));
memset(flag,,sizeof(flag));
int ans = ;
for(int i = ;i < k;++i)
for(int jk = ;jk <= min(m / guai[i].a,s / guai[i].b);++jk)
for(int j = m;j >= jk * guai[i].a;--j)
for(int k = s;k >= jk * guai[i].b;--k)
if(E[j][k] < E[j-jk * guai[i].a][k-jk * guai[i].b] + jk * guai[i].exp)
{
flag[i] = ;
E[j][k] = E[j-jk * guai[i].a][k-jk * guai[i].b] + jk * guai[i].exp;
if(E[j][k] >= n)
ans = min(ans,j);
}
if(E[m][s] >= n)
printf("%d\n",m - ans);
else printf("-1\n");
}
return ;
}