在求dp[i][j]的最优值的时候，我们比较了两个值的大小，一个是dp[i][j]，一个是dp[i][j-b[i]]+a[i]，之前我们直接抛弃掉其中一个，留下另一个就是dp[i][j]，现在我们不将其抛弃，而是将其记录。准确的说我们以前比较dp[i][j]和dp[i][j-b[i]]+a[i]，从中求出第一名，现在我们比较的是dp[i][j][1...K]和dp[i][j-b[i]][1...k]+a[i]，从中求出前K名。
思路：分别记录 dp[i][j] 中前K个解，和 dp[i][j-b[i]]+a[i] 中前K个解，那么从两个最有K个解中找出前K个解，这样就得到要求的第K个最优解。
注意：因为题目认为如果两个值相同，无论组合方式如何，都认为是一种情况，所以维护数组是要注意去掉值相同的。
1 #include<stdio.h> 2 #include<string.h> 3 int a[105],c[105],b[105],d[105],f[1005][35]; 4 int main() 5 { 6 int t,n,V,K; 7 int i,j,tt; 8 scanf("%d",&t); 9 while(t--) 10 { 11 scanf("%d%d%d",&n,&V,&K); 12 for(i=1;i<=n;i++) 13 scanf("%d",&a[i]); 14 for(i=1;i<=n;i++) 15 scanf("%d",&c[i]); 16 memset(f,0,sizeof(f)); 17 for(i=1;i<=n;i++) 18 { 19 for(j=V;j>=c[i];j--) 20 { 21 for(tt=1;tt<=K;tt++) 22 { 23 b[tt]=f[j][tt]; 24 d[tt]=f[j-c[i]][tt]+a[i]; 25 } 26 b[tt]=d[tt]=-1; 27 int x,y,z; 28 x=y=z=1; 29 while(z<=K&&(y<=K||x<=K)) 30 { 31 if(b[x]>d[y]) 32 f[j][z]=b[x++]; 33 else 34 f[j][z]=d[y++]; 35 if(f[j][z]!=f[j][z-1]) 36 z++; 37 } 38 } 39 } 40 printf("%d ",f[V][K]); 41 } 42 return 0; 43 } 44 /* 45 3 46 5 10 2 47 1 2 3 4 5 48 5 4 3 2 1 49 5 10 12 50 1 2 3 4 5 51 5 4 3 2 1 52 5 10 16 53 1 2 3 4 5 54 5 4 3 2 1 55 */