题意：求解01背包价值的第K优解。
分析：
基本思想是将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。
首先看01背包求最优解的状态转移方程：
\[dp\left[ j \right] = \max \left\{ {dp\left[ j \right],dp\left[ {j - a\left[ i \right].w} \right] + a\left[ i \right].v} \right\}\]如果要求第K优解，那么状态 dp[j] 就应该是一个大小为K的数组dp[j][1..K]。（其中dp[j][k]表示背包大小为j时，第k优解的值。 ）
Note:
dp[j]是一个大小为K的数组，或者也可以简单地理解为在原来的方程中加了一维。
我们将利用手段维护 dp[j][1..K] 的有序性，然后原方程就可以解释为：
\[dp\left[ j \right]\left[ {1 \ldots K} \right] = merge\left\{ {dp\left[ j \right]\left[ k \right],dp\left[ {j - a\left[ i \right].w} \right]\left[ k \right] + a\left[ i \right].v|0 \le k \le K} \right\}\]有序队列 dp[j-a[i].w]+a[i].v 则理解为在 dp[j-a[i].w][1..K] 的每个数上加上 a[i].v 后得到的有序队列。
合并这两个有序队列并将结果的前K项储存到dp[j][1..K]中的复杂度是O(K), 最后的答案是f[N] [V][K]。总的复杂度是O(VNK)。
---以上思路摘自
【问题】如何合并两个队列？
已知队列P[1…K],Q[1…K]，均为从大到小的顺序排列，求解队列R[1…K]是P，Q合并后的前K项。
首先，我们得考虑去重问题，故我们不能将P,Q队列合并再排序，取前K项了事。
我曾借助于STL中的SET，利用SET中的元素互异性解决去重问题，但很可惜超时。
精巧的解决方案：
//队列名为：alpha[1...K],beta[1...K]alpha[k+1]=-1;beta[k+1]=-1;int t=1,p=1,q=1;while(t<=k &&(p<=k && q<=k)){ if(alpha[p]>beta[q]) dp[j][t]=alpha[p++]; else dp[j][t]=beta[q++]; if(dp[j][t]!=dp[j][t-1]) t++;}Note：
- 这里要注意（p<=k || q<=k）不能写成（p<=k && q<=k），因为某一个队列取完元素，并不等价于我们取到了前K个元素。
- 我们需要初始化操作 alpha[K+1]=beta[K+1]=-1，只要初始化为负数均可。
我们知道背包中的解最小为0，不可能取负数，现在我们假设队列beta的下标q=k,且beta[p]=0，
表示队列beta已经取完了有效元素，而队列alpha中的下标p<k，但是alpha[p]=0.
那么下一轮循环中，条件if(alpha[p]>beta[q])不成立，会导致q++,数组下标溢出，导致循环提前异常退出，显然会导致结果出错。
所以我们这里必须初始化为负数，不可省略这一步。
- 同时为了达到去重效果，我们需要将t下标从1开始计数，否则我们将找不到dp[j][t-1]，导致程序异常终止，只有当前后两个数各异时，我们才移动下标t。
解答代码：
#include#include #include using namespace std;#define maxn_n 105#define maxn_v 1005#define maxn_k 35int dp[maxn_v][maxn_k];struct bone{ int v,w;};bone b[maxn_n];int alpha[maxn_k],beta[maxn_k];int main(){ //freopen("in.txt","r",stdin); int cases; scanf("%d",&cases); while(cases--){ int n,v,k; scanf("%d %d %d",&n,&v,&k); for(int i=1;i<=n;i++) scanf("%d",&b[i].v); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++){ scanf("%d",&b[i].w); for(int j=v;j>=b[i].w;j--){ for(int t=1;t<=k;t++){ alpha[t]=dp[j][t]; beta[t]=dp[j-b[i].w][t]+b[i].v; } alpha[k+1]=-1; beta[k+1]=-1; int t=1,p=1,q=1; while(t<=k &&(p<=k ||q<=k)){ if(alpha[p]>beta[q]) dp[j][t]=alpha[p++]; else dp[j][t]=beta[q++]; if(dp[j][t]!=dp[j][t-1]) t++; } } } printf("%d\n",dp[v][k]); }}