洛谷P1858 多人背包 题解

题目链接：P1858 多人背包

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

建议先去读一读《背包九讲》再来看

注意到朴素的 $01$ 背包是这样转移的

$$dp[j]=\max(dp[j],dp[j-w[i]]+v[i])$$

我们可以将其看作两个长度为 $1$ 的有序队列合并的结果

则考虑记录 $k$ 优解

在 $dp[j]$ 的基础上增加一维 $k$ ，即 $dp[j][k]$ ，表示 $k$ 优解

则每次将 $dp[j][k_1]$ 与 $dp[j-w[i]][k_2]+c[i]$ 合并

取最优的 $k$ 个解记录到 $dp[j][k_i]$ 即可

显然可以用归并排序来搞定

时间复杂度 $O(nmk)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e2+15)
#define M (int)(5e3+15)
#define K 55
int n,m,k;
int dp[M][K],w[N],v[N],t[K];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> k >> m >> n;
    for(int i=1; i<=n; i++)
        cin >> w[i] >> v[i];
    memset(dp,0xc0,sizeof(dp));
    dp[0][1]=0;
    for(int i=1; i<=n; i++)
        for(int j=m; j>=w[i]; j--)
        {
            int t1=1,t2=1,cnt=0;
            while(t1+t2<=k+1)
            {
                if(dp[j][t1]>dp[j-w[i]][t2]+v[i])
                {
                    t[++cnt]=dp[j][t1++];
                }else
                {
                    t[++cnt]=dp[j-w[i]][t2++]+v[i];
                }
            }
            for(int d=1; d<=cnt; d++)
                dp[j][d]=t[d];
        }
    int res=0;
    for(int i=1; i<=k; i++)
        res+=dp[m][i];
    cout << res << endl;
    return 0;
}