題目連結：https://vjudge.net/contest/103424#problem/H
題目大意：
與01背包模闆題類似，隻不過要我們求第K個最大的總價值。
解題分析：
其基本思想是将每個狀态都表示成有序隊列，将狀态轉移方程中的max/min轉化成有序隊列的合并。這裡仍然以01背包為例講解一下。
首 先看01背包求最優解的狀态轉移方程：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。如果要求第K優解，那麼 狀态f[i][v]就應該是一個大小為K的數組f[i][v][1..K]。其中f[i][v][k]表示前i個物品、背包大小為v時，第k優解的值。 “f[i][v]是一個大小為K的數組”這一句，熟悉C語言的同學可能比較好了解，或者也可以簡單地了解為在原來的方程中加了一維。顯然f[i][v] [1..K]這K個數是由大到小排列的，是以我們把它認為是一個有序隊列。
然 後原方程就可以解釋為：f[i][v]這個有序隊列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]這兩個有序隊列合并得到的。有序隊列 f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]則了解為在f[i-1][v-c[i]][1..K]的每 個數上加上w[i]後得到的有序隊列。合并這兩個有序隊列并将結果的前K項儲存到f[i][v][1..K]中的複雜度是O(K)。最後的答案是f[N] [V][K]。總的複雜度是O(VNK)。
01背包再清楚不過了，主要還是是有序隊列合并的問題。
這道題可以比喻為，要計算整個年級的前n名，可以拿每班的前n名出來排序
現在01背包的基礎上多加一維，dp[v][k]，表示在v空間下第k大的價值。。。
更新的時候有兩個數組A、B，然後合并AB，選出AB裡面前k個最大的。合并到dp中。。。
#include <iostream>
#include <cstdio>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn = 1005;
int main()
{
int T;
scanf("%d", &T);
int dp[maxn][33], val[maxn], vol[maxn], A[33], B[33];
while (T--)
{
int n, v, k;
scanf("%d %d %d", &n, &v, &k);
int i, j, kk;
for (i = 0; i<n; i++) scanf("%d", &val[i]);
for (i = 0; i<n; i++) scanf("%d", &vol[i]);
memset(dp, 0, sizeof(dp));
int a, b, c;
for (i = 0; i<n; i++)
for (j = v; j >= vol[i]; j--)
{
for (kk = 1; kk <= k; kk++)
{
A[kk] = dp[j - vol[i]][kk] + val[i];
B[kk] = dp[j][kk];
}
A[kk] = -1, B[kk] = -1; //定義邊界
a = b = c = 1;
while (c <= k && (A[a] != -1 || B[b] != -1))
{
if (A[a] > B[b]) //在兩個數中挑選較大的那個
dp[j][c] = A[a++];
else
dp[j][c] = B[b++];
if (dp[j][c] != dp[j][c - 1]) //反之，如果dp[j][c]==dp[j][c-1]的話,c的值不增加，等到下一個A或者B數組中的數，将dp[j][c]覆寫,作用是去除相同的情況
c++;
}
}
printf("%d\n", dp[v][k]);
}
return 0;
}