rt，教练讲了思路：

背包的第 $k$ 优解

普通的 01 背包求的是最优解，在普通的背包 DP 方法上稍作改动，增加以为用于记录当前状态下的前 $k$ 优解，即可得到求 01 背包第 $k$ 优解的算法。

具体的，设 $f_{i,j,k}$ 表示考虑前 $i$ 个物品，体积是 $j$ 的条件下，第 $k$ 优解的价值。

考虑原本的转移，$f_{i,j}=\max\{f_{i-1,j},f_{i-1,j-v_i}+w_i\}$。

• 所有不选 $i$ 的决策构成序列 $[f_{i-1,j,1},f_{i-1,j,2},\dots,f_{i-1,j,k}]$；

• 所有选 $i$ 的决策构成序列 $[f_{i-1,j-v_i,1}+w_i,\dots,f_{i-1,j-v_i,k}+w_i]$。

将两个序列合并即可得到 $f_{i,j,*}$。

时间复杂度 $O(nmk)$。

但是蒟蒻不会写代码。。。

help!