//完全背包,根据优化后的0-1背包
//时间复杂度仍为O(V*n),空间复杂度为O(V)
//不过可以处理一部分数据,就是“花费更大价值更小”的数据,这里我是用优先队列处理
//例题链接http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=2340

#include <stdio.h>

#define N 10010
#define M 10010
#define max(a,b) (a)>(b)?(a):(b)

typedef struct f{
    int c,w;
}Node;
Node node[N];
int dp[M],front[N];
int len;

void init(int n){
    int i;
    len=-1;
    for(i=0;i<n;i++){
        scanf(“%d%d”,&node[i].w,&node[i].c);
        while(len!=-1 && node[front[len]].w<=node[i].w && node[front[len]].c>=node[i].c)//花费更大价值更小,可舍弃
                len–;
        front[++len]=i;
    }
}
void solve(int k,int n){
    int i,j;
    init(n);
    for(i=0;i<=len;i++){
        for(j=node[front[i]].c;j<=k;j++)
            dp[j]=max(dp[j],dp[j-node[front[i]].c]+node[front[i]].w);
    }
    printf(“%d\n”,dp[k]);
}
int main(){
    int k,n;
    while(scanf(“%d%d”,&k,&n)!=EOF)
        solve(k,n);
    return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation