bbknapsack.java

用分支界限法解决的几个问题:包括0-1背包问题,最大团问题,电路布线问题,最大装载问题.作业最优处理问韪.

/*
 * BBKnapsack.java
 *
 * Created on 2006年4月16日, 下午9:34
 *
 * To change this template, choose Tools | Options and locate the template under
 * the Source Creation and Management node. Right-click the template and choose
 * Open. You can then make changes to the template in the Source Editor.
 */

package test;
import java.lang.*;
/**
 *
 * @author michael
 */
public class BBKnapsack {
    static double c;        //背包的容量
    static int n;//物品总数
    static double[] w;//物品重理数组
    static double[] p;//物品价值数组
    static double cw;//当前重量
    static double cp;//当前价值
    static int [] bestx;//最优解
    static double bestp;// 最优价值    
    static Maxheap heap;//活结点优先队列 
    /** Creates a new instance of BBKnapsack */
    public BBKnapsack(){}
    
 private static double bound(int i){
      double cleft = c - cw;
      double bound = cp;
      while(i <= n-1 && w[i] <= cleft){
       cleft -= w[i];
       bound += p[i];
       i++;
      }
      if(i < n)bound += p[i]/w[i]*cleft;
      return bound;
 }
    
    private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch){
        //将一个新的活结点插入到子集树的最大堆 H 中
        BBnode b=new BBnode(par,ch);
        HeapNode node=new  HeapNode(b,up,pp,ww,lev);
        heap.insert(node);
    }
    private static double bbKnapsack(){
        //优先队列式分支限界法，返回最大价值，beatx返回最优解
        //初始化
        BBnode enode=null;
        int i=1;
        double bestp=0.0;  //当前最优值
        double up=bound(1);//价值上界
        
        //搜索子集空间树
        while (i!=n+1){
            //非叶子结点
            //检查当彰扩展结点的左儿子结点
            double wt=cw+w[i];
            if (wt<=c){
                //左儿子结点为可行结点
                if (cp+p[i]>bestp)
                    bestp=cp+p[i];
                addLiveNode(up, cp+p[i],cw, i+1,enode,true);
            }
            up=bound(i+1);
            //检查当前扩展结点的右儿子结点
            if(up>=bestp)
                //右子树可能含最优解
                addLiveNode(up, cp, cw,i+1,enode,false);
            //取下一个扩展结点
            HeapNode node=(HeapNode)heap.removeMax();
            enode=node.liveNode;
            cw=node.weight;
            cp=node.profit;
            up=node.upperProfit;
            i=node.level;
        }
        //构造最优解
        for (int j=n;j>0;j--){
            bestx[j]=(enode.leftChild)?1:0;
            enode=enode.parent;
        }
        return cp;
    }
    public  double knapsack(double[] pp,double[] ww,double cc,int[] xx){
        //返回最大价值,bestx 返回最优解
        c=cc;
        n=pp.length-1;
    
        //定义依单位重量价值排序的物品数组
        Element[] q=new Element[n];
        double ws=0.0;
        double ps=0.0;
        for (int i=1;i<=n;i++){
            q[i-1]=new Element(i,pp[i]/ww[i]);
            ps+=pp[i];
            ws+=ww[i];
        }
        System.out.println("ws="+ws+",c="+c);  
        if (ws<=c) { // 所有物品装包
            for (int i=1;i<=n;i++) xx[i]=1;
            return ps;
        }
        
        //依单位重量价值排序
        MergeSort.sort(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-1].id];
        }
        cw=0.0;
        cp=0.0;
        bestx=new int[n+1];
        heap=new Maxheap();
        
        //调用bbKnapsack 求问题的最优解
        double maxp=bbKnapsack();
        for(int i=1;i<=n;i++)
             xx[q[n-i].id]=bestx[i];
        return maxp;
    }
  public  double knapsack(double[] pp,double[] ww,double cc){
      //返回最大价值,bestx 返回最优解
      c = cc;
      n = pp.length;
      cw = 0.0;
      cp=0.0;
      bestp=0.0;
      Element[] qq = new Element[n];
      bestx = new int[n+1];
      for (int i =1; i <= n;i++)
        qq[i-1] = new Element(i-1,pp[i-1]/ww[i-1]);
      for(int i =1;i <= n ;i++)
        System.out.print(","+qq[i-1].d);   //打印单位价格
      System.out.println();
      MergeSort.sort(qq);//按单位重量背包价值排序，从小到大
      for(int i=n-1; i>= 0;i--)
      {
         System.out.print(qq[i].id);//按从大到小输出查看
         System.out.println(qq[i].d);
      }
      System.out.println();
      p = new double[n];
      w = new double[n];
      for(int i = 0; i < n; i++)
      {
       p[i] = pp[qq[n-i-1].id];

      //根据排序结果以从大到小，从新对价值和重量赋值
       w[i] = ww[qq[n-i-1].id];
      }
      backtrace(0);// recuision diaoyong
      System.out.println("0-1 problem current bestp as recuision solution ="+bestp);
      for(int i = 0 ; i< n;i++)
       System.out.print(bestx[i]);
       for(int i = 0 ; i< n;i++)
       if (bestx[i]==1) System.out.print(qq[i].id);
      return bestp;
 }
 private static void backtrace(int i){
     // 递归搜索解空间的子集树
     

      if(i > n-1){
       bestp = cp;
       return;   //完成
      }
      if(cw + w[i] <= c){
       cw += w[i];
       cp += p[i];
       for (int j=0;j<n;j++) bestx[j]=0;
       System.out.println("push  "+i+"cp="+cp+"bestp="+bestp);
       backtrace(i+1);
       System.out.println("pop  "+i+"cp="+cp+"bestp="+bestp);
       bestx[i]=1;
       cw -= w[i];
       cp -= p[i];
      }
      if(bound(i+1) > bestp){
        //分支，对不符合bound函数的右子树剪
        backtrace(i+1);

      }
 }
}