洛谷P1858 【多人背包】 (背包求前k优解)

题目描述：

重点：求 01 背包前 k 优解的价值和，并且背包要装满。

算法分析：

首先，01 背包大家应该很熟悉了，这里就不讲转移式了。

先讲第一部分：如何保证背包装满？

正常的 01 背包是从数组初始值为 0 开始，也就是说每一种体积都会转移，有可能会更新答案。

但如果要装满，显然，装不满的体积(也就是没有 n 个物品的体积和能为这个体积)显然不能要。似乎感觉很难，但没关系，我们把 f 数组先赋值为最小值。

这样有什么好处？会发现，因为是一层一层往下刷，那么第一层显然只有体积正好为第一个物品的那个体积，会更新最大值(因为别的都是负无穷，不会更新)。

然后开始刷第二层，显然，只有在第一层刷过的那个体积，才会接着往后转移(因为转移别的都是从负无穷转移过来的，没有意义，不可能是最大值)。

然后注意 ff 数组要有一个初始值是 0 (后面讲)。

来看第二部分：求前 k 优解的价值和。

设 f[i][j] 表示体积为 i，第 j 优解的值。这时，上面说的 f 数组初始值就可以赋值了。把 f[0][1] 赋值为 0，因为体积为 0 的最优解显然是 0。

我们需要考虑前 k 优解。从最优解开始往后找。

01 背包是 f[j] 和 f[j−w[i]]+v[i] 的转移，那么这道题可以借鉴这种思路。

设 x，y 分别为两边的最优解。如果 f[j][x]>f[j−w[i]][y]，我们用一个数组 rnk 来存前 k 优解，这时 rnk[++cnt]=f[j][x]，并且把 x+1。反之同理。

这段话表示什么？就是记录这两种背包的容量，哪一种是大的。

最后在外面把 f 数组在容积为 j 的条件下的前 k 优解赋值为 rnk 数组的前 k 个就可以了。

总代码：

#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48) ; ch=getchar();}
    return x*f;
}
inline void print(int x){
    if(x/10) print(x/10);
    putchar(x%10+'0');
}
const int M = 5010;
int k,value,n,ans;
int w[M],v[M],f[M][60],rnk[M];
signed main(){
    k=read(),value=read(),n=read();
    for(re int i(1) ; i<=n ; ++i) scanf("%d%d",&w[i],&v[i]);
    memset(f,-0x7f7f7f7f,sizeof(f));
    f[0][1] = 0;
    for(re int i(1) ; i<=n ; ++i){
        for(re int j(value) ; j>=w[i] ; --j){
            int rn1=1,rn2=1,cnt=0;
            while(cnt<=k){
                if(f[j][rn1] > f[j-w[i]][rn2]+v[i]){
                    rnk[++cnt] = f[j][rn1];
                    rn1++;
                }
                else{
                    rnk[++cnt] = f[j-w[i]][rn2]+v[i];
                    rn2++;
                }
            }
            for(re int h(1) ; h<=k ; ++h) f[j][h] = rnk[h];
        }
    }
    for(re int i(1) ; i<=k ; ++i) ans += f[value][i];
    printf("%d",ans);
    return 0;
}