其实这个问题，真的挺好想的，但是我咋想了那么久呢~~
很好理解，第K大01背包一定基于01背包，dp数组也很容易的想到由dp[V] ----> dp[V][K],来表示背包容量是V时候的第K大背包
然后就是状态转移方程了，多写一写，你也能手推出来的，不能被吓到
dp[V][1] = max_第一大（dp[v][1],dp[v-w][1]+vi）
dp[V][2] = max_第二大数(dp[v][1],dp[v-w][1]+vi,dp[v][2],dp[v-w][2]+vi) = max_第二大数(dp[v][1],dp[v][2],dp[v-w][2]+vi)
从而得到一般式子
dp[v][k] = max_第K大(dp[v][1],dp[v][2],....dp[v][k],dp[v-w][1]+vi,.....dp[v-w][k]+vi
明白了这两个，代码方面就比较好实现了
可以用排序来进行
但是一看排列，发现取第K大值分为两部分，且排列都是降序，所以我们可以用两个数组存储起来，然后进行赋值（复杂度也比较低）
/*
dp[x][y]表示的是容量为x的第k大值
所以dp[x][1] = max_(第一大值){dp[x][1],dp[x-v][1]+w}
dp[x][2] = max_(第二大值){dp[x][1],dp[x][2],dp[x-v][1]+w,dp[x-v][2]+w}
依次类推~~
*/
/*
因为dp[j][1]...dp[j][k]与dp[j-w[i]][1]+v[i]...dp[j-w[i]][k]+v[i]
是依次递减的，那么我们可以用两个数组将这两组数组保存起来，
再O(N)的时间内求得第K大。
*/
#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1005;
int dp[maxn][maxn];
int n,W,K;//W:总容量值，K第K大值
int v[maxn],w[maxn];//价值，一个为体积
int s1[maxn],s2[maxn];
void KthZeroOnePack()
{
for(int i = 0;i < n;i++)//遍历了每一个物品
{
for(int j = W;j >= w[i];j--)//层铺每一层体积
{
for(int th = 1;th <= K;th++)//求取前k大值
{
//0 - k-1 到K结束
s1[th-1] = dp[j][th];//遍历存储每一个可能取到的值，且s1是递减的
s2[th-1] = dp[j - w[i]][th] + v[i];//遍历存储每一个可能取到的值，且s2是递减的
}
//特判结束点
s1[K] = s2[K] = -1;
int cnt = 1,cnt1 = 0,cnt2 = 0;
//从第一大开始
while(cnt <= K && (s1[cnt1] != -1 || s2[cnt2] != -1))
{
if(s1[cnt1] > s2[cnt2])dp[j][cnt] = s1[cnt1++];
else dp[j][cnt] = s2[cnt2++];
//严格递减
if(dp[j][cnt] != dp[j][cnt-1]) cnt++;
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&W,&K);
memset(dp,0,sizeof(dp));
for(int i = 0;i < n;i++)
{
scanf("%d",&v[i]);
}
for(int i = 0;i < n;i++)
{
scanf("%d",&w[i]);
}
KthZeroOnePack();
printf("%d
",dp[W][K]);
}
return 0;
}