0-1リュック問題-分岐限界法

分岐限界法は遡及法とよく似ており,異なる点は遡及法は深さ優先探索を用い,分岐限界法は広さ優先探索を用い,キューを用いて有効ノードがあるたびに有効ノードを記録し,入隊出隊により有効ノードを遍歴する.分岐限界法は,活結点から次の拡張ノードを選択する際の異なる方法によって異なる分岐限界法をもたらし,キュー分岐限界法と優先キュー分岐限界法がよく見られるが,ここではキュー内分岐限界法を例に挙げる.
下辺のコード設計は部分的に分かりにくいが,ここでは特に説明する:分岐限界法を用いて01バックパックを解く場合,同層ノードのサブノードはいずれも同一物品の「装着」と「装着しない」の2つの状態であるため,ノードの深さ(すなわち物資の位置)を記録することによって仮想的な木が構築される.(ここで仮想ツリーとは、各ノードが親ノードまたは子ノードとの関係を保存していないため、ポインタやjavaの属性値でツリーを巡回することはできない)を指す.この設計では、ツリーを構築するプロセスを回避し、論理的に仮想ツリーを巡回することを直接判断することができる.

package test;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by saishangmingzhu on 2018/11/26.
 */
public class Rucksack {

    //【1】      
    //【2】         
    public static void main(String[] arg) {
        new Rucksack().branchAndBoundMethod();
    }

    /**
     *      -   
     */
    public void branchAndBoundMethod() {
        int rucksackV=10;
        List goodsList=new ArrayList<>();
        goodsList.add(new Goods(" ",1,2));
        goodsList.add(new Goods("  ",3,4));
        goodsList.add(new Goods("   ",7,2));
        goodsList.add(new Goods("macbook",3,6));
        goodsList.add(new Goods("iphone",1,5));
        goodsList.add(new Goods("  ",5,3));
        goodsList.add(new Goods("   ",4,2));
        int goodsListSize=goodsList.size();
        //【1】        ，       、    、     
        //【2】     
        Node root=new Node();
        root.setSurplusV(rucksackV);
        root.setWorth(0);
        root.setLevel(0);
        Node parentNode=root;
        //【3】    
        List queueNodeList=new ArrayList<>();
        List queueLeafNodeList=new ArrayList<>();
        queueNodeList.add(parentNode);
        while (queueNodeList.size()>0){
            parentNode=queueNodeList.get(0);
            System.out.println("("+parentNode.getWorth()+","+parentNode.getSurplusV()+")");
            int nextLevel=parentNode.getLevel()+1;
            if (nextLevel>goodsListSize){
                queueLeafNodeList.add(parentNode);
            } else {
                Goods g = goodsList.get(parentNode.getLevel());
                int surplus = parentNode.getSurplusV() - g.getVolume();
                if (surplus >= 0) {
                    Node node = new Node();
                    node.setLevel(nextLevel);
                    node.setSurplusV(surplus);
                    node.setWorth(parentNode.getWorth() + g.getWorth());
                    queueNodeList.add(node);
                }
                Node node = new Node();
                node.setLevel(nextLevel);
                node.setSurplusV(parentNode.getSurplusV());
                node.setWorth(parentNode.getWorth());
                queueNodeList.add(node);
            }
            queueNodeList.remove(0);
        }
        int maxV=0;
        for (Node node:queueLeafNodeList){
            System.out.print(node.getWorth()+",");
            if (maxV