(Java)分支界限法求解背包问题

淡淡的烟草味﹌ 2022-09-17 11:19 172阅读 0赞

1.代码

package com.test;
    import java.util.*;
    
    public class Main {
    	
    	
    	
    static double c; 
    static int n;
    static double w[];
    static double p[];
    static double cw;
    static double cp;
    static int bestX[];
    static MaxHeap heap;
    //上界函数bound计算结点所相应价值的上界
    private static double bound(int i){
      double cleft=c-cw;
      double b=cp;
      while(i<=n&&w[i]<=cleft){
       cleft=cleft-w[i];
       b=b+p[i];
       i++;
      }
                    //装填剩余容量装满背包
      if(i<=n)
       b=b+p[i]/w[i]*cleft;
      return b;
    }
            //addLiveNode将一个新的活结点插入到子集树和优先队列中
    private static void addLiveNode(double up,double pp,double ww,int lev,BBnode par,boolean ch){
      //将一个新的活结点插入到子集树和最大堆中
                    BBnode b=new BBnode(par,ch);
      HeapNode node =new HeapNode(b,up,pp,ww,lev);
      heap.put(node);
    }
    private static double MaxKnapsack(){
                //优先队列式分支限界法，返回最大价值，bestx返回最优解
      BBnode enode=null;
      int i=1;
      double bestp=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+w[i],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 static 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=0;i<n;i++){
       q[i]=new Element(i+1,pp[i+1]/ww[i+1]);
       ps=ps+pp[i+1];
       ws=ws+ww[i+1];
      }
      if(ws<=c){
       return  ps;
      }           
      p=new double[n+1];
      w=new double[n+1];
      for(int i=0;i<n;i++){
       p[i+1]=pp[q[i].id];
       w[i+1]=ww[q[i].id];
      }
      cw=0.0;
      cp=0.0;
      bestX = new int[n+1];
      heap = new MaxHeap(n);
      double bestp = MaxKnapsack();
      for(int j=0;j<n;j++)
       xx[q[j].id]=bestX[j+1];
      
      return  bestp;
      
    }
    public static void main(String [] args){
      double w[]=new double[4];
      w[1]=16;w[2]=15;w[3]=15;
      double v[]=new double[4];
      v[1]=45;v[2]=25;v[3]=25;
      double c=30;
      int x[] = new int[4];
      double m = knapsack(v,w,c,x);
    //  System.out.println("请输入物器数：");
    //  Scanner sc=new Scanner(System.in);
    //  n=sc.nextInt();
    //  System.out.println("请输入包容容量：");
    //  c=sc.nextDouble();
    //  System.out.println("请输入物品数组：3个int");
    //  w[0]=sc.nextDouble();
    //  w[1]=sc.nextDouble();
    //  w[2]=sc.nextDouble();
    //  System.out.println("请输入价值数组3个int：");
    //  v[0]=sc.nextDouble();
    //  v[1]=sc.nextDouble();
    //  v[2]=sc.nextDouble();
      
      System.out.println("*****分支限界法*****");
         System.out.println("*****物品个数：n="+n);
         System.out.println("*****背包容量：c="+c);
         System.out.println("*****物品重量数组：w= {"+w[0]+" "+w[1]+" "+w[2]+"}");
         System.out.println("*****物品价值数组：v= {"+v[0]+" "+v[1]+" "+v[2]+"}");
        System.out.println("*****最优值：="+m);
        System.out.println("*****选中的物品是:");
      for(int i=1;i<=3;i++)
       System.out.print(x[i]+" ");
      }
    }
    
    //子空间中节点类型
    class BBnode{
    BBnode parent;//父节点
    boolean leftChild;//左儿子节点标志
    
    BBnode(BBnode par,boolean ch){
      parent=par;
      leftChild=ch;
    }
    }
    
    class HeapNode implements Comparable{
    BBnode liveNode; // 活结点
    double upperProfit; //结点的价值上界
    double profit; //结点所相应的价值
    double weight; //结点所相应的重量
    int level; // 活结点在子集树中所处的层次号
    
    //构造方法
    public HeapNode(BBnode node, double up, double pp , double ww,int lev){
      liveNode = node;
      upperProfit = up;
      profit = pp;
      weight = ww;
      level = lev;
    }
    public int compareTo(Object o) {
    
      double xup = ((HeapNode)o).upperProfit;
      if(upperProfit < xup)
       return -1;
      if(upperProfit == xup)
       return 0;
      else
       return 1;
    }
    }
    
    class Element implements Comparable{
    int id;
    double d;
    public 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;
    }
    public boolean equals(Object x){
      return d==((Element)x).d;
    }
    }
    class MaxHeap{
      static HeapNode [] nodes;
      static int nextPlace;
      static int maxNumber;
      public MaxHeap(int n){
       maxNumber = (int)Math.pow((double)2,(double)n);
       nextPlace = 1;//下一个存放位置
       nodes = new HeapNode[maxNumber];
      }
      public static void put(HeapNode node){
       nodes[nextPlace] = node;
       nextPlace++;
       heapSort(nodes);
      
      }
      public static HeapNode removeMax(){
       HeapNode tempNode = nodes[1];
       nextPlace--;
       nodes[1] = nodes[nextPlace];
       heapSort(nodes);
       return tempNode;
      }
      private static void heapAdjust(HeapNode [] nodes,int s,int m){
       HeapNode rc = nodes[s];
       for(int j=2*s;j<=m;j*=2){
       
        if(j<m&&nodes[j].upperProfit<nodes[j+1].upperProfit)
         ++j;
       
        if(!(rc.upperProfit<nodes[j].upperProfit))
         break;
        nodes[s] = nodes[j];
        s = j;
       }
       nodes[s] = rc;
      }
      private static void heapSort(HeapNode [] nodes){
       for(int i=(nextPlace-1)/2;i>0;--i){
      
        heapAdjust(nodes,i,nextPlace-1);
       }
      }
    }

2.结果：

*****分支限界法*****
    *****物品个数：n=3
    *****背包容量：c=30.0
    *****物品重量数组：w= {15.0 16.0 15.0}
    *****物品价值数组：v= {25.0 45.0 25.0}
    *****最优值：=50.0
    *****选中的物品是:
    0 1 1