HDU-2639-Bone Collector II

链接：https://vjudge.net/problem/HDU-2639#author=Zxzz106

题意：

给v大的背包，n个物品的价值和体积，求能装下的第k大的价值是多少。

01背包，第k大。

思路：

dp数组多开一维记录从第一大到第k大的值。

内循环用两个数组记录使用当前物品和不使用当前物品的情况。

结束后将两个数组合并到dp数组中。

代码：

#include <iostream>
#include <memory.h>
#include <vector>
#include <map>
#include <algorithm>
#include <cstdio>
#include <math.h>

using namespace std;

typedef long long LL;

const int MAXN = 1e2 + 10;
const int MAXV = 1e3 + 10;
const int MAXK = 30 + 5;

int dp[MAXV][MAXK];
int a[MAXN];
int b[MAXN];
int A[MAXK];
int B[MAXK];

int main()
{
    int t;
    int n, v, k;
    scanf("%d", &t);
    while (t--)
    {
        memset(dp, 0, sizeof(dp));
        scanf("%d%d%d", &n, &v, &k);
        for (int i = 1;i <= n;i++)
            scanf("%d", &a[i]);
        for (int i = 1;i <= n;i++)
            scanf("%d", &b[i]);

        for (int i = 1;i <= n;i++)
            for (int j = v;j >= b[i];j--)
            {
                for (int x = 1;x <= k;x++)
                {
                    A[x] = dp[j - b[i]][x] + a[i];
                    B[x] = dp[j][x];
                }
                A[k + 1] = -1;
                B[k + 1] = -1;
                int x, y, z;
                x = y = z = 1;
                //对得到的所有价值排序入队
                while (x <= k && (A[y] != -1 || B[z] != -1))
                {
                    if (A[y] > B[z])
                        dp[j][x] = A[y++];
                    else
                        dp[j][x] = B[z++];
                    if (dp[j][x] != dp[j][x - 1])
                        x++;
                }
            }

        printf("%d
", dp[v][k]);
    }

    return 0;
}