随笔-141  评论-9  文章-3  trackbacks-0
pku 3628 Bookshelf 2 (01背包)

题目意思是给你n个数，其中选取一些数使他们的和sum大于给定数M，求满足此条件的Min{M-sum},此题可以装化为01背包问题，刚开始可以把所有的数都加起来这时的sum一定大于M的，但此时的sum-M不一定是最小的，怎么才能得到最小的呢。可以这样想，令B=sum-M，要尽量在这B中减去一些原来加进去数，这样会使sum-M的差逐渐减小，这不就是01背包的模型吗，背包的容量为B，物品的价值与体积相同。尽量使其价值最大，那最后的到的差当然就是最小的。

#include <iostream>

using namespace std;

int N,H;

int cows[25];
int f[1000001];

int inline max(int a, int b){
    return a>b?a:b;
}

int main(){
    int sum=0, i,j;
    cin>>N>>H;

    for(i=1; i<=N; ++i){
        cin>>cows[i];
        sum+=cows[i];
    }

    int m = sum - H;

    for(i=1; i<=N; ++i)
        //ZeroOnePack(w[i], c[i])
        for(j=m; j>=cows[i]; --j)
            f[j]=max(f[j], f[j-cows[i]]+cows[i]);


    cout<<m-f[m]<<endl;
    return 0;
}


参考:http://hi.baidu.com/zhouxc07/blog/item/898a103c35b886ce9e3d6262.html
posted on 2010-12-08 11:21 小阮 阅读(244) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮