给定背包容量，骨头的个数和每个骨头的价值，这次不是求在背包容量允许的情况下，最多装的价值，而是求在背包容量内，可以装的第k大价值，如果没有第k个最大值，那么输出0

输入包括多组样例，第一行输入一个T,样例的个数，接下来每个样例都有三行，第一行包括三个整数，N,V,K,分别代表骨头的个数，背包的容量，我们需要输出的第K个最大值，

第二行包括N个数，分别代表骨头的数量和接下来一行有N个数，分别表示每种骨头的价值。

输出第K个最大价值，每个样例输出一行

​

​

思路

常规的0-1背包是求V体积下能装的物品的最大价值，而本题求的是第K大价值。

常规0-1背包的状态转移公式：dp[j]=max(dp[j],dp[j-w[i]]+v[i])

而本题的区别是要求第K大价值，于是将数组升级为二维dp[V][K]，表示背包容量为V能装下的第K大价值，对于每一个V都保存着K个值，从大到小排序。

还是一样的二重循环，然后多加一重循环，对于dp[j]，需要计算dp[j-bone[i].b]+bone[i].a，然后对dp[j-bone[i].b]+bone[i].a的K个值与dp[j]的K个值进行合并，合并后得到的新的K个值返回保存dp[j]中。

这样就可以实现背包的K优解的计算，最后输出dp[V][K]（K从1开始）。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;

const int MAXN1 = 1005;
const int MAXN2 = 35;

int dp[MAXN1][MAXN2];
int q1[MAXN2], q2[MAXN2];

struct node{
    int a;
    int b;
} bone[MAXN1];

int main(){
    int T;
    scanf("%d", &T);
    while(T--){
        int N, V, K;
        int x,y,z;
        scanf("%d%d%d", &N, &V, &K);
        for (int i = 0; i < N; i++){
            scanf("%d", &bone[i].a);
        }
        for (int i = 0; i < N; i++){
            scanf("%d", &bone[i].b);
        }
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < N; i++){
            for(int j=V; j>=bone[i].b; j--){
                for(int p=1; p<=K; p++){
                    q1[p] = dp[j][p];
                    q2[p] = dp[j-bone[i].b][p]+bone[i].a;
                }
                q1[K+1]=q2[K+1]=-1;
                x=y=z=1;
                while(z<=K && (q1[x]!=-1 || q2[y]!=-1)){
                    if(q1[x]>q2[y]) dp[j][z] = q1[x++];
                    else dp[j][z] = q2[y++];
                    if(dp[j][z]!=dp[j][z-1]) z++;
                }
            }
        }
        printf("%d\n", dp[V][K]);
    }
    return 0;
}