hdu 2639Bone Collector II 背包的第K优解问题
Problem DescriptionInputOutputSample InputSample Output????#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;int bag[1000+10][55],val[101],n,v,k,vol[102],used[1000+10],a[55],b[55];void _01bag(){int i,j,t,x,y,z;memset(used,0,sizeof(used));memset(bag,0,sizeof(bag));memset(a,0,sizeof(a));memset(b,0,sizeof(b)); for(i=0;i<n;i++)for(j=v;j>=vol[i];j--){for(t=1;t<=k;t++){a[t]=bag[j][t];b[t]=bag[j-vol[i]][t]+val[i];}x=y=z=1;while(z<=k&&(x<=k||y<=k)){if(a[x]>=b[y]){bag[j][z]=a[x]; x++;}else {bag[j][z]=b[y];y++;}if(bag[j][z]!=bag[j][z-1]) z++;}}printf("%d\n",bag[v][k]);}int main(){ int i,cas; scanf("%d",&cas);while(cas--){scanf("%d %d %d",&n,&v,&k);for(i=0;i<n;i++) scanf("%d",&val[i]);for(i=0;i<n;i++) scanf("%d",&vol[i]);_01bag(); } return 0;}

参考了宇宙吾心