洛谷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;
}