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][], 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, -);met(b, -);

        met(dp, );met(v, );met(w, );

        scanf("%d %d %d", &n, &W, &K);

        for(int i=; i<=n; i++)

            scanf("%d", &v[i]);

        for(int i=; i<=n; i++)

            scanf("%d", &w[i]);

        for(int i=; i<=n; i++)

        {

            for(int j=W; j>=w[i]; j--)

            {

                for(int k=; k<=K; k++)///寻找容量为j的前k个最优解合成的最优解

                {

                    a[k]=dp[j][k];

                    b[k]=dp[j-w[i]][k]+v[i];

                }

                int p=, q=, r=;

                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-]) r++;

                }

            }

        }

        printf("%d\n", dp[W][K]);

    }

    return ;

}