随笔-141  评论-9  文章-3  trackbacks-0
pku 2624 Charm Bracelet (01背包)
很标准的01 背包问题

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

#include <iostream>

using namespace std;

int w[3500], d[3500];
int f[13000];
int N,M;

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

int main(){
    int i,j;
    cin>>N>>M;

    for(i=1; i<=N; ++i)
        cin>>w[i]>>d[i];

    for(i=1; i<=N; ++i)
        // ZeroOnePack(w[i], d[i])
        for(j=M; j>=w[i]; j--)
            f[j] = max(f[j], f[j-w[i]]+d[i]);
    
    cout<<f[M]<<endl;

    return 0;
}

posted on 2010-12-07 16:05 小阮 阅读(148) 评论(0)  编辑 收藏 引用 所属分类: POJ

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


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