Bone Collector II---hdu2639（01背包求第k优解）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2639

求01背包的第k大解。

合并两个有序序列

选取物品i，或不选。最终的结果，是我们能在O(1)的时间内，判定对于体积j，是否应当选取第i件物品。

我们在这里作出了最优的选择。那被我们抛弃的选择呢？他很可能是次优解，第三优解，无论怎样，他都对我们本题求前K优解，起到了重要的作用！

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<iostream>
using namespace std;
#define N 1500
#define met(a, b) memset(a, b, sizeof(a))

int dp[N][35], v[N], w[N], W, n, K;
int a[N], b[N];
///dp[j][k]表示容量为j的第k大的值；
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        met(a, -1);met(b, -1);
        met(dp, 0);met(v, 0);met(w, 0);

        scanf("%d %d %d", &n, &W, &K);
        for(int i=1; i<=n; i++)
            scanf("%d", &v[i]);
        for(int i=1; i<=n; i++)
            scanf("%d", &w[i]);

        for(int i=1; i<=n; i++)
        {
            for(int j=W; j>=w[i]; j--)
            {
                for(int k=1; k<=K; k++)///寻找容量为j的前k个最优解合成的最优解
                {
                    a[k]=dp[j][k];
                    b[k]=dp[j-w[i]][k]+v[i];
                }

                int p=1, q=1, r=1;
                while(r<=K && (p<=K||q<=K))///合并重新生成前k个最优解
                {
                    if(a[p]>b[q]) dp[j][r]=a[p++];
                    else dp[j][r]=b[q++];
                    if(dp[j][r]!=dp[j][r-1]) r++;
                }
            }
        }
        printf("%d
", dp[W][K]);
    }
    return 0;
}