Bone Collector II 背包，01背包 Bone Collector II
Time Limit : 5000/2000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 19 Accepted Submission(s) : 17
Here is the link:http://acm.hdu.edu.cn/showproblem.php?pid=2602
Today we are not desiring the maximum value of bones,but the K-th maximum value of the bones.NOTICE that,we considerate two ways that get the same value of bones are the same.That means,it will be a strictly decreasing sequence from the 1st maximum , 2nd maximum .. to the K-th maximum.
If the total number of different values is less than K,just ouput 0.
Followed by T cases , each case three lines , the first line contain two integer N , V, K(N <= 100 , V <= 1000 , K <= 30)representing the number of bones and the volume of his bag and the K we need. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.
5 10 2
1 2 3 4 5
5 4 3 2 1
5 10 12
1 2 3 4 5
5 4 3 2 1
5 10 16
1 2 3 4 5
5 4 3 2 1
2
0
#include<stdio.h>
long c[1001][31],x,t1[31],t2[31];
void unite(long i)
{
long j,k,l,flag;
k=1;l=1;
for(j=1;j<=x;j++)
{
if(k>x&&l>x)
break;
while(flag==0)
{
if(t1[k]>t2[l])
{
if(t1[k]!=c[i][j-1])
{
c[i][j]=t1[k];
k++;
flag=1;
}
else
k++;
}
else
{
if(t2[l]!=c[i][j-1])
{
c[i][j]=t2[l];
l++;
flag=1;
}
else
l++;
}
if(k>x&&l>x)
break;
}
flag=0;
}
}
int main()
{
long t,n,v,i,j,k,l,a[101],b[101];
while(scanf("%ld",&t)!=EOF)
{
for(i=1;i<=t;i++)
{
scanf("%ld%ld%ld",&n,&v,&x);
for(j=1;j<=n;j++)
scanf("%ld",&a[j]);
for(j=1;j<=n;j++)
scanf("%ld",&b[j]);
for(j=0;j<=v;j++)
for(k=0;k<=x;k++)
c[j][k]=0;
t1[x+1]=-1;t2[x+1]=-1;
for(j=1;j<=n;j++)
for(k=v;k>=b[j];k--)
{
for(l=1;l<=x;l++)
{
t1[l]=c[k-b[j]][l]+a[j];
t2[l]=c[k][l];
}
unite(k);
}
printf("%ld
",c[v][x]);
}
}
}