题意：求01背包的第k最优值
输入：第一行为T，下面是T组数据，每组数据有n,m,k 代表n件物品，m容量，和题目要求的k，下一行是n个物品的价值，再一行是n个物品的体积
输出：T行答案
/* 类似于归并排序中合并的做法，对于f[i][j]的k个最优值，从f[i-1][j]和f[i-1][j-w[i]]+v[i] 的k个最优值中选出最优的k个放入 */ #include<cstdio> #include<iostream> #include<cstring> #define N 110 #define M 1010 using namespace std; int f[M][N/3],v[N],w[N],x[M],y[M],n,m,k; int read() { char c=getchar();int num=0; while(c<'0'||c>'9'){c=getchar();} while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();} return num; } void work() { n=read();m=read();k=read(); for(int i=1;i<=n;i++) v[i]=read(); for(int i=1;i<=n;i++) w[i]=read(); for(int i=1;i<=n;i++) for(int j=m;j>=w[i];j--) { for(int l=1;l<=k;l++) x[l]=f[j][l],y[l]=f[j-w[i]][l]+v[i]; int s1=1,s2=1,s3=1; x[k+1]=y[k+1]=-1; while((x[s1]!=-1||y[s2]!=-1)&&s3<=k) { if(x[s1]>y[s2])f[j][s3]=x[s1++]; else f[j][s3]=y[s2++]; if(f[j][s3]!=f[j][s3-1])s3++; } } printf("%d ",f[m][k]); } int main() { int T;scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); work(); } return 0; }