描述 Description
约翰的干草库存已经告罄，他打算为奶牛们采购日 (1≤日≤50000) 磅干草．
他知道 N(1≤N≤100)个干草公司，现在用 1 到 N 给它们编号．第 i 个公司卖的干草包重量为 Pi(1≤Pi≤5000)磅，需要的开销为 Ci(l≤Ci≤5000)美元．每个干草公司的货源都十分充足，可以卖出无限多的干草包． 帮助约翰找到最小的开销来满足需要，即采购到至少 H 磅干草．
输入格式 InputFormat
第 1 行输入 N 和日，之后 N 行每行输入一个 Pi 和 Ci．
输出格式 OutputFormat
最小的开销．
样例输入 SampleInput
4 30
8 28
13 27
26 24
13 10
样例输出 SampleOutput
30
来源 Source
Silver
代码 Code
完全背包问题，注意是至少要采购到 H 磅干草。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define inf 0x7fffffff/27.11
const int maxp=500000;
int p[101],c[101];
int f[500001];
int i,j,t,n,m,l,r,k,z,y,x,ans;
int main()
{
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++) scanf("%d%d",&p[i],&c[i]);
for (i=1;i<=maxp;i++) f[i]=inf;
f[0]=0;
for (i=1;i<=n;i++)
{
for (j=p[i];j<=maxp;j++)
{
f[j]=min(f[j],f[j-p[i]]+c[i]);
}
}
ans=inf;
for (i=m;i<=maxp;i++) ans=min(ans,f[i]);
printf("%d\n",ans);
return 0;
}