PKU--3628 Bookshelf 2（01背包）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目http://poj.org/problem?id=3628

分析：给定一堆牛的高度，把牛叠加起来的高度超过牛棚的高度。

且是牛叠加的高度与牛棚高度之差最小。

把牛叠加的高度看作是背包的容量，利用01背包计算所能达到的最大值。

然后在最大值里面选择一个与牛棚高度差值最小的。

在开辟dp[]数组的时候没有必要开辟20*1000000不然会超过内存，适当小一点即可。


     
      
       #
       
        include
       
       <stdio.h>
       

       #
       
        include
       
       <string.h>
       

       

       
        const
       
       
        int
       
       INF=0XFFFFFF;
       

       

       
        int
       
       dp[2000002];
       

       

       
        int
       
       main()
       

       {
       

       
        int
       
       N,B,sum,h[21];
       

       
        while
       
       (scanf("%d%d",&N,&B)!=EOF)
       

       {
       

       //读取数据，并计算牛叠加高度
       

       sum=0;
       

       
        for
       
       (
       
        int
       
       i=1;i<=N;i++)
       

       {
       

       scanf("%d",&h[i]);
       

       sum+=h[i];
       

       }
       

       

       //初始化，不需要装满
       

       memset(dp,0,
       
        sizeof
       
       (dp));
       

       

       //求所能达到的最大高度
       

       
        for
       
       (
       
        int
       
       i=1;i<=N;i++)
       

       
        for
       
       (
       
        int
       
       j=sum;j>=h[i];j--)
       

       dp[j]=dp[j]>dp[j-h[i]]+h[i]?dp[j]:dp[j-h[i]]+h[i];
       

       

       //计算差值最小的
       

       
        int
       
       min=INF;
       

       
        for
       
       (
       
        int
       
       i=B;i<=sum;i++)
       

       
        if
       
       (dp[i]>=B&&dp[i]-B<=min) min=dp[i]-B;
       

       

       printf("%d\n",min);
       

       }
       

       
        return
       
       0;
       

       }