装载问题-回溯法

冷不防 2022-10-02 10:53 197阅读 0赞

有两艘货船，载重分别为w1、w2，物品总重量不超过载重总量w1+w2，问物品是否都可以装下。如，w1=w2=10，物品g1=g2=9，g3=2，则无法装下；w1=w2=5，w3=10，则可以装下。

这是个典型的装载问题，多箱多物可否容纳。思路是尽可能将前边的箱子装满，判断剩余物品是否可以装入最后一个箱子。

package test;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.List;
    
    /**
     * Created by zuohao on 2018/11/30.
     */
    public class BinPackingProblem {
    
        private List<Node> nodeList=new ArrayList<>();
    
        public static void main(String[] arg) {
    //        new BinPackingProblem().greedy();
            new BinPackingProblem().backtracking();
        }
    
        /**
         * 回溯算法
         * 建立左右子结点是为了形成物理上的树结构，实际对应这个算法可以不建立左右子结点，因为构建树和计算结果同步进行，获得结果后就停止了，不会再次使用构建好的树
         */
        public void backtracking(){
            int rucksackWeight1=10;
            int rucksackWeight2=10;
            List<Goods> goodsList=new ArrayList<>();
            goodsList.add(new Goods("书",1));
            goodsList.add(new Goods("足球",3));
            goodsList.add(new Goods("大箱子",7));
            goodsList.add(new Goods("macbook",3));
            goodsList.add(new Goods("iphone",1));
            goodsList.add(new Goods("礼盒",5));
    //        //装不下的情况
    //        goodsList.add(new Goods("书",2));
    //        goodsList.add(new Goods("足球",9));
    //        goodsList.add(new Goods("大箱子",9));
            int allWeight=0;
            for (Goods goods:goodsList){
                allWeight=allWeight+goods.getWeight();
            }
            if (allWeight>rucksackWeight1+rucksackWeight2){
                System.out.println("物品总重量已超出两货船总承载");
                return;
            }
            //【1】装第一艘货船，尽可能多的装
            Node parentNode=new Node();
            parentNode.setSurplusWeight(rucksackWeight1);
            again(goodsList, parentNode,0);
            Collections.sort(nodeList, new Comparator<Node>() {
                @Override
                public int compare(Node o1, Node o2) {
                    int surplus=o1.getSurplusWeight()-o2.getSurplusWeight();
                    if (surplus<0)
                        return -1;
                    else if (surplus>0)
                        return 1;
                    return 0;
                }
            });
            Node first=nodeList.get(0);
            if (allWeight-(rucksackWeight1-first.getSurplusWeight())<=rucksackWeight2){
                System.out.println("两货船可以装下所有物品");
                System.out.println("第一艘货船需装如下物品，其余物品装第二艘货船");
                List<Goods> goodsList1=first.getGoodsList();
                for (Goods goods:goodsList1){
                    System.out.print(goods.getName()+",");
                }
                System.out.println();
            }
            else {
                System.out.println("两货船无法装下所有物品");
            }
    
    
        }
    
        private void again(List<Goods> goodsList, Node parentNode,int i) {
            if (i>=goodsList.size()){
                nodeList.add(parentNode);
                return;
            }
            Goods goods=goodsList.get(i);
            int surplus=parentNode.getSurplusWeight()-goods.getWeight();
            if (surplus>=0){
                Node leftNode=new Node();
                leftNode.setSurplusWeight(surplus);
                parentNode.setLeftNode(leftNode);
                leftNode.getGoodsList().addAll(parentNode.getGoodsList());
                leftNode.getGoodsList().add(goods);
                again(goodsList,leftNode,i+1);
            }
            Node rightNode=new Node();
            rightNode.setSurplusWeight(parentNode.getSurplusWeight());
            parentNode.setRightNode(rightNode);
            rightNode.getGoodsList().addAll(parentNode.getGoodsList());
            again(goodsList,rightNode,i+1);
        }
    
        class Goods{
            private String name;
            private int weight;
    
            public Goods(String name, int weight) {
                this.name = name;
                this.weight = weight;
            }
    
            public String getName() {
                return name;
            }
    
            public void setName(String name) {
                this.name = name;
            }
    
            public int getWeight() {
                return weight;
            }
    
            public void setWeight(int weight) {
                this.weight = weight;
            }
        }
    
        class Node{
            private int surplusWeight;
            private Node leftNode;
            private Node rightNode;
            private List<Goods> goodsList=new ArrayList<>();
    
            public int getSurplusWeight() {
                return surplusWeight;
            }
    
            public void setSurplusWeight(int surplusWeight) {
                this.surplusWeight = surplusWeight;
            }
    
            public Node getLeftNode() {
                return leftNode;
            }
    
            public void setLeftNode(Node leftNode) {
                this.leftNode = leftNode;
            }
    
            public Node getRightNode() {
                return rightNode;
            }
    
            public void setRightNode(Node rightNode) {
                this.rightNode = rightNode;
            }
    
            public List<Goods> getGoodsList() {
                return goodsList;
            }
    
            public void setGoodsList(List<Goods> goodsList) {
                this.goodsList = goodsList;
            }
        }
    }

转载于:https://blog.51cto.com/zuohao1990/2324831