随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.1.6 Stamps (可重背包)

其实类似可重背包问题,   f[i] = min {f[i-cost[j]] + 1}  

i表示背包容量,

cost[j]表示 第j种物品的消耗.

/*
ID: lorelei
TASK: stamps
LANG: C++
*/

#include <fstream>

using namespace std;

const int MAXF = 2000000;
const int MAXN = 55;
const int INF = 0x7FFFFFFF;

int f[MAXF], cost[MAXN];
int N, K;

int main(){
    int i,j;

    ifstream fin("stamps.in");
    ofstream fout("stamps.out");

    fin>>K>>N;

    f[0] = 0 ;

    for(i=1; i<MAXF; ++i)
        f[i] = INF;

    for(i=1; i<=N; ++i)
        fin>>cost[i];

    for(j=1; j<MAXF; ++j){
        for(i=1; i<=N; ++i){
            if(cost[i]<=j && f[j-cost[i]]+1 < f[j])
                f[j] = f[j-cost[i]]+1;
        }
        if(f[j]>K){
            fout<<j-1<<endl;
            break;
        }
    }
    
    return 0;
}

posted on 2010-12-20 11:14 小阮 阅读(133) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


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