背包的第 $k$ 优解

背包的第 \(k\) 优解

Bone Collector II

简化题意

同标题，求背包的第 \(k\) 优解。废话

思路

正常背包记录的就是最大值，转移用的也是最大值，但现在我们需要的是第 \(k\) 优解，那么我们就记录全部的由前 \(k\) 种最优解的到的所有可能，然后进行排序，就能得到全部的第 \(k\) 优解。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 1e2+10;
constexpr int maxv = 1e3+10;
constexpr int maxk = 35;int dp[maxv][maxk];    // dp[i][j]容量为i的第j大值
int vi[maxn],wi[maxn]; // 价值，重量
int tmpa[maxk],tmpb[maxk]; // 记录两个状态的前k大signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endif // ONLINE_JUDGEint t,n,m,k;scanf("%lld",&t);for(int tr=1;tr<=t;++tr){memset(dp,0,sizeof dp);// 多测清空scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=n;++i){scanf("%lld",vi+i);}for(int i=1;i<=n;++i){scanf("%lld",wi+i);}for(int i=1;i<=n;++i){for(int j=m;j>=wi[i];--j){for(int kk=1;kk<=k;++kk){tmpa[kk]=dp[j][kk];// 存储两种转移的所有可能tmpb[kk]=dp[j-wi[i]][kk]+vi[i];}tmpa[k+1]=-1, tmpb[k+1]=-1;int a=1,b=1,c=1;// a，b的指针，dp[j]的指针while(c<=k && (~tmpa[a] || ~tmpb[b]))// 不到k，且a，b都还有{if(tmpa[a]>tmpb[b])// 取更大值{dp[j][c]=tmpa[a++];}else{dp[j][c]=tmpb[b++];}if(dp[j][c]!=dp[j][c-1])// 要求严格递减{++c;}}}}printf("%lld\n",dp[m][k]);}return 0;
}