01背包的前k优解

发表于

原题地址

题目描述

求01背包前k优解的价值和

输入输出格式

输入格式：

第一行三个数K、V、N

接下来每行两个数，表示体积和价值

输出格式：

前k优解的价值和

输入输出样例

输入样例#1：

1
2
3
4
5
6
2 10 5
3 12
7 20
2 4
5 6
1 1

输出样例#1：

1
57

说明

对于100%的数据,K≤50,V≤5000,N≤200

题解

对于普通的01背包

f[j]=max(f[j],f[j-w[i]]+c[i])

f[j]是由f[j-w[i]]转移的

我们加一维k优解

则f[j][k]是由f[j][]和f[j-w[i]][]转移而来的

由于k很小，只需要暴力判断

但是，这样的背包必须装满，应原题要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<cstring>
int f[5010][60],ans=0;
int k,v,n,w[220],c[220],t[60];
int main(){
    memset(f,128,sizeof(f));
    scanf("%d%d%d",&k,&v,&n);
    for (int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]);
    f[0][1]=0;
    for (int i=1;i<=n;i++)
        for (int j=v;j>=w[i];j--){
            int t1=1,t2=1,t[60],len=0;
            while (t1+t2<=k+1){
        if (f[j][t1]>f[j-w[i]][t2]+c[i]) 
            t[++len]=f[j][t1++];
                else t[++len]=f[j-w[i]][t2++]+c[i];
            }
            for (int K=1;K<=k;K++) f[j][K]=t[K];
        }
    for (int i=1;i<=k;i++) ans+=f[v][i];
    printf("%d",ans);
}