1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<set> 6 #include<vector> 7 #include<map> 8 #include<algorithm> 9 #include<cmath>10 #include<stdlib.h>11 using namespace std;12 int main()13 {14     int t,n,v,kk,i,j;15     int dp[1010][75];16     int va[1010],vo[1010];17     cin>>t;18     while(t--)19     {20         cin>>n>>v>>kk;21         memset(dp,0,sizeof(dp));22         for(i=0;i<=v;i++)    //dp[i][0] 表示容量为 i 的价值种类数23         dp[i][0]=1;24         for(i=1; i<=n; i++)25             cin>>va[i];26         for(i=1; i<=n; i++)27             cin>>vo[i];28 29         for(i=1;i<=n;i++)30         for(j=v;j>=vo[i];j--){31             int cnt=dp[j][0];32             for(int k=1;k<=dp[j-vo[i]][0];k++)33                 dp[j][++cnt]=dp[j-vo[i]][k]+va[i];34             int tmp[70],num=1;35             for(int k=1;k<=cnt;k++)36             tmp[k]=dp[j][k];37             sort(tmp+1,tmp+1+cnt);      //对价值进行排序，之后取前kk个价值，如果不足则全取38             dp[j][1]=tmp[cnt];39             for(int k=cnt-1;k>=1;k--)   //取前kk个价值，如果不足则全取40             if(tmp[k]!=tmp[k+1])41             {42                 if(num+1>kk)43                 break;44                 dp[j][++num]=tmp[k];45             }46             dp[j][0]=num;47         }48         if(dp[v][0]<kk)49         cout<<0<<endl;50         else51         cout<<dp[v][kk]<<endl;52     }53 }