class Element implements Comparable{
int id;
double d;
Element(int idd,double dd){
id=idd;
d=dd;
}
public int compareTo(Object x){
double xd=((Element)x).d;
if(d<xd) return -1;
if(d==xd) return 0;
return 1;
}
}

class Mergesort {
Mergesort come=new Mergesort();
public static void mergeSort(Comparable a[],int left,int right)
{
if(left<right)
int i=(left+right)/2;
mergeSort(a,left,i);
mergeSort(a,i+1,right);
come.merge(a,b,left,i,right);
come.copy(a,b,left,right);
}
public static void merge(Comparable []c,Comparable []d,int l,int m,int r)
{
int i=1;
j=m+1,
k=1;
while(i<=m)&&(j<=r))
if(c[i].compareTo(c[j])<=0)
d[k++]=c[i++];
else d[k++]=c[j++];
if(i>m)
for(int q=j;q<=r;q++)
d[k++]=c[q];
else
for(int q=i;q<=m;q++)
d[k++]=c[q];
}
public static void copy(Comparable []a,Comparable []b,int left,int right){
for(int i=left;i<=right;i++)
a[i]=b[i];
}
}

public class Knapsack
{
static double c=7;
static int n=4;
static double []w={0,3,5,2,1};
static double []p={0,9,10,7,4};
static double cw;
static double cp;
static double bestp;
Mergesort newcome=new Mergesort();
public static double knapsack(double []pp,double []ww,double cc)
{
c=cc;
n=pp.length-1;
cw=0.0;
cp=0.0;
bestp=0.0;
Element []q=new Element[n];
for(int i=1;i<=n;i++)
q[i-1]=new Element(i,pp[i]/ww[i]);
newcome.mergeSort(q);
p=new double[n+1];
w=new double[n+1];
for(int i=1;i<=n;i++)
{
p[i]=pp[q[n-i].id];
w[i]=ww[q[n-i].id];
}
newcome.backtrack(1);
return bestp;
}
private static void backtrack(int i){
Knapsack l=new Knapsack();
if(i>n)
{
bestp=cp;
return;
}
if(cw+w[i]<=c)
{
cw+=w[i];
cp+=p[i];
backtrack(i+1);
cw-=w[i];
cp-=p[i];
}
if(l.bound(i+1)>bestp)
backtrack(i+1);
}

private static double bound(int i){
double cleft=c-cw;
double bound=cp;
while(i<=n&&w[i]<=cleft)
{
cleft-=w[i];
bound+=p[i];
i++;
}
if(i<=n)
bound+=p[i]*cleft/w[i];
return bound;
}
public static void main(String args[]){
Knapsack result=new Knapsack();
static double value=result.knapsackp(p,w,c);
System.out.println(value);
}
}

嗯，谢谢，我昨天又重新检查了一遍，发现了很多错误，修改后可以通过了，我发现了很多有趣的经验，但不又知该怎么表达了，想分享却又不知从何说起，不过，谢谢了