学步园

第二道二维背包，1A，虽然简单，但是每次1A都很开心~~~~~

刚开始的时候题目看错了，想了个三维的出来，还打出来了呢。。。不知道对不对。。。。然后再看一看发现是二维的。。。

然后发现自己对于完全背包和0-1背包的顺序问题还有点混乱。等我再领悟领悟。。。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

#define maxn 110
int dp[maxn][maxn],ex[maxn],red[maxn];
int n,m,t,s,ans,inf;
int solve()
{
    int i,j,k;
    memset(dp,0,sizeof(dp));
    for(i=1;i<=t;i++)
        for(j=1;j<=s;j++)
        for(k=red[i];k<=m;k++)
        dp[j][k]=max(dp[j][k],dp[j-1][k-red[i]]+ex[i]);
    int tmp=inf;
    for(i=0;i<=m;i++)
    {
        if(dp[s][i]>=n) tmp=min(tmp,i);
    }
    if(tmp==inf) return 0;
    ans=m-tmp;
    return 1;
}
int main()
{
    inf=0x3f3f3f3f;
    while(scanf("%d%d%d%d",&n,&m,&t,&s)!=EOF)
    {
        for(int i=1;i<=t;i++) scanf("%d%d",&ex[i],&red[i]);
        if(!solve()) printf("-1\n");
        else printf("%d\n",ans);
    }
    return 0;
}