回溯法实现01背包问题JAVA版.txt

package shiyan4;
import java.util.*;
public class Knapsack01pa { 
/* 
   用回溯法解决0-1背包问题  
   */ 
private double[] p,w;//分别代表价值和重量
private int n;
private double c,bestp,cp,cw;
private int x[]; //记录可选的物品
private int[] cx;
public Knapsack01pa(double pp[],double ww[],double cc){
   this.p=pp;this.w=ww;this.n=pp.length-1;
   this.c=cc;this.cp=0;this.cw=0;
   this.bestp=0;
   x=new int[ww.length];
   cx=new int[pp.length];
}
void knapsack(){
   backtrack(0);
}
void backtrack(int i){
   if(i>n){             //判断是否到达了叶子节点
    if(cp>bestp){
     bestp=cp;
     for(int j=0;j<x.length;j++)
      x[j]=cx[j];
    }
    return;
   }