用回溯法求解0/1背包问题

输出如下：

背包所盛放物品的最大价值为：
60
所盛放物品编号为
[1, 2]

代码如下：

package AlgorithmTest;

import java.util.ArrayList;
import java.util.Collections;

/**  * Created by dell on 2016/12  *用回溯法求解01背包问题，回溯法可以求解最优解问题和求出多个符合要求的解。关键是要讲问题的解空间转换成数，使得树的一条路径就是一个解。.  */ public class BagProblem {
    public static void main(String[] args) {
        int[] weights = new int[]{18, 14, 16};//三个物品的重量  int[] vaules = new int[]{48, 30, 30};//三个物品的价值  int bagHodler = 30;//bag的承重为30，想要知道将将那些物品放入bag中能使价值最大，且不超重  SolveSpaceTree solveSpaceTree = new SolveSpaceTree(weights, vaules, bagHodler);
        Result result = solveSpaceTree.getSolve();
        System.out.println("背包所盛放物品的最大价值为：");
        System.out.println(result.value);
        System.out.println("所盛放物品编号为");
        System.out.println(result.ojectNos.toString());


    }

    //解空间树  private static class SolveSpaceTree{
        private int bagHolder;
        private TreeNode[] nodes;
        public SolveSpaceTree(int[] weights, int[] values, int bagHodler){
            this.bagHolder = bagHodler;
            nodes = new TreeNode[(int)Math.pow(2, weights.length + 1) - 1];
            nodes[0] = new TreeNode(-1, false, 0, 0);//第一个节点是空几点不代表哪个物品  int index = 1;
            for (int i = 0; i < weights.length; i++){
                for (int j = 0; j <= i; j++){
                    nodes[index++] = new TreeNode(i, false, weights[i], values[i]);
                    nodes[index++] = new TreeNode(i, true, weights[i], values[i]);
                }
            }
        }
        public Result getSolve(){
            ArrayList<Result> results = new ArrayList<Result>();
            getSolve(0, new Result(), results);
            Collections.sort(results);
            return results.get(results.size() - 1);
        }
        public void getSolve(int node, Result result, ArrayList<Result> results){
            if (node >= nodes.length){
                results.add(result);
                return ;
            }

            int currentWeight = nodes[node].occur? nodes[node].weight: 0;
            int currentValue = nodes[node].occur? nodes[node].value: 0;
            if (currentWeight + result.weightSum <= this.bagHolder){//符合约束条件，往下走  if (nodes[node].occur){
                    Result result1 = new Result();
                    result1.weightSum = currentWeight + result.weightSum;
                    result1.value = currentValue + result.value;
                    result1.ojectNos.addAll(result.ojectNos);
                    result1.ojectNos.add(nodes[node].objectNo);
                    getSolve(2 * node + 1 ,result1, results);
                    getSolve(2 * node + 2 ,result1, results);
                }else{
                    getSolve(2 * node + 1 ,result, results);
                    getSolve(2 * node + 2 ,result, results);
                }
            }else{
                if (result.weightSum <= this.bagHolder){
                    results.add(result);
                }
            }
        }


    }

    public static class Result implements Comparable<Result>{
        private int weightSum = 0;
        private int value = 0;
        private ArrayList<Integer> ojectNos = new ArrayList<Integer>();
        @Override
        public int compareTo(Result o){
            return this.value - o.value;
        }
    }

    public static class TreeNode{
        private boolean occur;//出现与否  private int weight;//重  private int value;//价值  private int objectNo;//节点代码的物品   public TreeNode(int objectNo, boolean occur, int weight, int value) {
            this.occur = occur;
            this.weight = weight;
            this.value = value;
            this.objectNo = objectNo;
        }
    }


}