这道题与Bone Collector的不同之处在于，这道题求的是第k优解，而非最优解。那应该怎么做呢？
首先，01背包的核心方程式dp[j] = max(dp[j] , dp[j - w[i]] + v[i]) ,也就是说，每一个新状态都是由dp[j]或dp[j - w[i]] + v[i]转移来的。我们首先用一个数组a[]和一个数组b[]将这两个状态存起来，然后再循环求得第k优解。这个过程有点像是，一个年级有两个班，我需要知道全年级的前十名是谁，那我就可以通过得到第一个班的前十是谁和第二个班的前十是谁来求得全年级的前十。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define mst(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int val[1005];
int wei[1005];
int a[1005],b[1005];
int dp[1005][31];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
mst(dp,0);
int n,vtot,k;
scanf("%d %d %d",&n,&vtot,&k);
for(int i=0;i<n;i++) cin>>val[i];
for(int i=0;i<n;i++) cin>>wei[i];
for(int i=0;i<n;i++)
{
for(int j=vtot;j>=wei[i];j--)
{
for(int q=0;q<k;q++)
{
a[q]=dp[j][q];
b[q]=dp[j-wei[i]][q]+val[i];
}
a[k]=-1;b[k]=-1;
int idx1=0;int idx2=0;int idx3=0;
while((idx1<k||idx2<k)&&idx3<k)
{
a[idx1]>b[idx2]?dp[j][idx3]=a[idx1++]:dp[j][idx3]=b[idx2++];
if(idx3==0||dp[j][idx3-1]!=dp[j][idx3]) //这个判断是防止有重复数据
idx3++;
}
}
}
cout<<dp[vtot][k-1]<<endl;
}
return 0;
}