POJ 3628 Bookshelf 2【01背包】

题意：给出n头牛的身高，以及一个书架的高度，问怎样选取牛，使得它们的高的和超过书架的高度最小。

将背包容量转化为所有牛的身高之和，就可以用01背包来做===

#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<algorithm>
#define maxn 2000005  
using namespace std;
int dp[maxn],h[50];
int main()
{
    int n,b,i,j,sum=0,tmp=1000010;
    scanf("%d %d",&n,&b);
    for(i=1;i<=n;i++) 
    {
        scanf("%d",&h[i]);
        sum+=h[i];
    }
    for(i=1;i<=n;i++)
    {
        for(j=sum;j>=h[i];j--)
        {
            dp[j]=max(dp[j],dp[j-h[i]]+h[i]);
            {
                if(dp[j]>=b&&j<tmp)
                tmp=j;
            }
        }
    }
    printf("%d
",tmp-b);    
}