分支限界法解决零一背包问题_分支限界求解0/1背包问题

1、零一背包问题

1.1概述

在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为V1,V2……Vn。最后选可行解中价值最大的解。

1.2问题分析

 零一背包问题不同于背包问题，背包问题的物件可分。
        在解决背包问题时，可以直接使用贪心法进行求解，思路也容易理解：先将物品的性价比进行排序，然后从高到低进行选取，保证选取的物品是当前最优选择。由于物件可分得缘故，所以每一步都可行。因此每一步可行以及每一步的最优达成了整个问题的最优（贪心法的使用需要证明）。
         回到零一背包问题，它不具有贪心的特征。不能直接使用贪心算法，对比背包问题，01背包问题仅仅是缺少了并不是每一步选取都可行的特性，但他仍然满足可行的局部最优解就是全局最优解。因此，只需要在贪心的实现上加入回溯，不可行则回溯。

1.3零一背包问题的图解 

零一背包问题的名字也体现了他的特征，选择结果只有0和1。
       利用这种思想，可以将问题看作一棵树，每一个为物品都为一个解点，每个节点都有两个选择：0或1，也就是选与不选

       最后一层为所有答案的集合，未必都是可行解，但可行解一定在其中。如果暴力求解，时间复杂度为2^n。

2、分支限界法

       2.1分支限界法的概述

分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
       在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。所以在解决类似问题时，需要加入优先队列或者栈的操作，来储存元素。
       分支限界法的思想可以简单理解为：贪心算法+回溯算法+权值

2.2分支限界法解决01背包问题

根据问题特性和算法特性做如下操作：

     1、首先需要将性价性价比进行排序。
                  对物品的选取顺序为高性价比到底性价比，这就保证了每一步为最大的性价比。

      2、为了保证每一步的选取都可行，需要构造限界函数。
                  当前操作是否可行，当前物品的质量，是否已经大与背包剩余容量的判断

      3.每次在进行选取后，到底该往哪边走的判断，这里加入权值ub。
                 ub：当权选择后的价值上限  ub=当前价值+剩余质量*未装入物品的最大性价比

2.3操作总结

分支限界法就是贪心和回溯的结合，再往前说就是是暴力求解的优化。将不能使用贪心求解的问题，加入限界函数。这里加入的权值，目的是为了能够在选取后能更好的选择方向。不加入权值也行，直接规定：每次深度优先树时，优先左子树，或者右子树。

2.4使用的数据结构和构造的类

在遍历树的过程中，需要储存树的节点，每个节点有自己的层数，在有全权值的情况下，每个节点有自己的权值，也就是访问的顺序，这里需要使用优先队列或者栈，使用栈时需要在进栈操作上进行选择。

构造的类：1.物品类，将物品的属性信息都加入其中
 

构造物品{
              属性1：编号
              属性2：质量
              属性3：价值
              属性4：性价比
           }

                 2.栈的节点类

构造队列节点{  优先队列的元素
              属性1：记录表 访问记录
              属性2：最大价值
              属性3：层数
              属性4：当前价值
              属性5：当前质量
 
           }

 

3、实例分析

3.1问题：

0/1背包问题。假设有4个物品，其重量分别为(4, 7, 5,3)， 价值为(40, 42, 25, 12)，背包容量W=10。首先，将物品按单位重量价值从大到小排序，结果如下:

                                                 

3.2执行树

4、java代码

public class EX {
    private static int NUM=0;
    private int weight_MAx;
    EX(int weight_MAx,int V[], int W[]){
        this.weight_MAx=weight_MAx;//先获取到质量
        fuzhi(V,W);//赋值排序同时进行
    }
    private  Weight weights[];
    private class Weight{
        int v;//价值
        int w;//质量
        double p;//性价比
        int num;//编号
        Weight(int v,int w){
            num=++NUM;
            this.v=v;
            this.w=w;
            p=v/w;
        }
    }
    private class Element{
        //优先队列中的元素
        boolean isOne[]=new boolean[weights.length];//对应物品数组 是否被录用
        double ub=weight_MAx*weights[0].p;;//最大初始价值
        int v=0;//当前价值
        int w=0;//当前质量
        int n=0;//所处树的层数
        public Element(){
        }
        private Element(boolean isOne[],double ub,int v,int w,int n){
            this.isOne=isOne;
            this.ub=ub;
            this.v=v;
            this.w=w;
            this.n=n;
        }
        Element newElement(boolean isOne){//下一层
            if(n+1==weights.length){
                n++;
                return null;
            }
            double ub;
            int v=this.v, w=this.w,n=this.n;
            if(isOne){
                v+=weights[n].v;
                w+=weights[n].w;
            }
            this.isOne[n]=isOne;
            if( ++n<weights.length)
                ub=(weight_MAx-w)*weights[n].p+v;
            else ub=w;
            return new Element(this.isOne,ub,v,w,n);
        }
    }
    public int[] F(){
        int mubiao[]=new int[weights.length];
        Element e=new Element();//开始
        Element E[]=new Element[20];//将优先队列 转化为栈 栈中最多可能性为：层数
        int top=-1;
        E[++top]=e;//进栈操作
        System.out.println("进栈操作");
        print(e);
        while (true){//当遍历到底时结束
 
            Element temp=E[top--];//将栈弹栈
            System.out.println("出栈操作");
            print(temp);
            Element nweElement1=temp.newElement(false);
            Element nweElement2=null;
            if(temp.n==weights.length)
            {
                System.out.println("遍历结束");
                for(int i=0;i<mubiao.length;i++)
                {
                    if(temp.isOne[i]){
                        mubiao[i]=weights[i].num;
                    }
                }
                return mubiao;
            }
            if((weight_MAx-temp.w)>=weights[temp.n].w){
                nweElement2=temp.newElement(true);
            }
            if (nweElement2==null)//优先左边
            {
                E[++top]=nweElement1;
                System.out.println("进栈操作");
                print(nweElement1);
            }
            else if(nweElement1.ub<=nweElement2.ub){
 
                E[++top]=nweElement1;
                E[++top]=nweElement2;
                System.out.println("进栈操作");
                print(nweElement1);
                System.out.println("进栈操作");
                print(nweElement2);
            }
            else {
                E[++top]=nweElement2;
                E[++top]=nweElement1;
                System.out.println("进栈操作");
                print(nweElement2);
                System.out.println("进栈操作");
                print(nweElement1);
            }
        }
    }
    private void fuzhi(int V[], int W[]){
        weights=new Weight[V.length];
        for(int i=0;i<W.length;i++)
        {
            weights[i]=new Weight(V[i],W[i]);
            int key = i;
            Weight value=weights[i];
            while(key > 0 && weights[key-1].p<value.p)
            {
                weights[key] = weights[key-1];
                key --;
            }
            weights[key]= value;
        }
    }
    private void print( Element e){
        if (e==null){
            return;
        }
        System.out.println("操作物品的所处树的层数："+e.n+" 该层物品是否装：入"+e.isOne[e.n]+"在该层时的价值："+e.v+"在该层时的质量："+e.w+"预测最大价值："+e.ub);
    }
}
class Test{
    public static void main(String[] args) {
 
        int V[]={12,40,42,25};//价值
        int W[]={3,4,7,5};//质量
        System.out.println("背包信息");
        for(int i=0;i<V.length;i++)
        {
            System.out.println("编号："+(i+1)+"质量"+W[i]+"价值"+V[i]);
        }
        int weight=10;//背包总重
        EX e=new EX(weight,V,W);
        int mubioa[]=e.F();
        System.out.print("背包录用编号：");
        for(int i:mubioa)
        {
            if(i!=0)
                System.out.print(i+"  ");
        }
    }
}

执行结果图：