编辑代码

import java.util.*;

public class Exp7_Knapsack {
    static int capacity; // 背包容量
    static int n; // 物品数量
    static int[] weights; // 物品重量
    static int[] values; // 物品价值
    static int curWeight; // 当前重量
    static int curValue; // 当前价值
    static int bestValue; // 当前最优价值
    static int[] bestx; // 在得到最优价值时的最优解
    static Element[] q;
    static PriorityQueue<HeapNode> heap; // 大顶堆
    static int btNum; // 回溯算法访问的节点个数
    static int bbNum; // 分支限界算法访问的节点个数

    public static void main(String[] args) {
        // 手动输入数据和自动生成数据必须二选一，也就是下面两个中注释掉一个
        manualGenerate();
        // randomGenerate();

        long t1 = System.nanoTime();
        int res1 = backtrackSolve();
        long t2 = System.nanoTime();
        int res2 = bbSolve();
        long t3 = System.nanoTime();

        System.out.println("回溯法：可装物品的最大价值：" + res1 + "，访问的节点个数：" + btNum + "，消耗时间（纳秒）：" + (t2 - t1));
        System.out.println("分支限界法：可装物品的最大价值：" + res2 + "，访问的节点个数：" + bbNum + "，消耗时间（纳秒）：" + (t3 - t2));
        System.out.println("最优解为：");
        printArray(bestx);
    }

    public static void manualGenerate() {
        Scanner scan = new Scanner(System.in);
        System.out.print("请输入背包容量：");
        int c = scan.nextInt();
        System.out.print("请输入物品个数：");
        int n = scan.nextInt();
        int[] w = new int[n + 1];
        int[] v = new int[n + 1];
        System.out.println("请输入物品重量（空格分隔）：");
        for (int i = 1; i < n + 1; i++) {
            w[i] = scan.nextInt();
        }
        System.out.println("请输入物品价值（空格分隔）：");
        for (int i = 1; i < n + 1; i++) {
            v[i] = scan.nextInt();
        }
        initial(v, w, c);
    }

    public static void randomGenerate() {
        Scanner scan = new Scanner(System.in);
        Random random = new Random();
        System.out.print("请输入物品个数：");
        int n = scan.nextInt();
        int[] w = new int[n + 1];
        int[] v = new int[n + 1];

        // 单个物品的最大重量
        int maxWeight = 0;
        // 总重量
        int sumWeight = 0;

        // 随机生成物品重量和价值
        for (int i = 1; i <= n; i++) {
            w[i] = random.nextInt((int) (1.2 * n)) + 1;
            maxWeight = Math.max(w[i], maxWeight);
            sumWeight += w[i];
            v[i] = Math.abs(random.nextInt(10) - 5 + w[i]);
        }

        // 随机生成背包容量，背包容量要大于单个物品的最大重量，小于总重量
        int c = random.nextInt(sumWeight - maxWeight) + maxWeight;
        System.out.println("物品重量为：");
        printArray(w);
        System.out.println("物品的价值为：");
        printArray(v);
        System.out.println("背包容量为：" + c);
        initial(v, w, c);
    }

    // 对用户输入的数据进行初始化，校验
    public static void initial(int[] vValue, int[] wWeight, int cCapacity) {
        capacity = cCapacity;
        n = vValue.length - 1;
        curWeight = 0;
        curValue = 0;
        bestValue = 0;
        bestx = new int[n + 1];

        // q为单位重量价值数组
        q = new Element[n];
        double ws = 0.0;
        double ps = 0.0;

        // 初始化q[0:n-1]
        for (int i = 1; i <= n; i++) {
            q[i - 1] = new Element(i, (double) vValue[i] / wWeight[i]);
            ps += vValue[i];
            ws += wWeight[i];
        }

        if (ws <= capacity) {
            System.out.println("背包容量大于物品所有重量之和，可以全部装下，最大价值为：" + ps);
            System.exit(0);
        }

        // 将各物品依单位重量价值从大到小排序
        Arrays.sort(q);

        values = new int[n + 1];
        weights = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            values[i] = vValue[q[n - i].id];
            weights[i] = wWeight[q[n - i].id];
        }
    }

    // 回溯算法解决问题的入口
    public static int backtrackSolve() {
        backtrack(1);
        return bestValue;
    }

    // 分支限界法解决问题的入口
    public static int bbSolve() {
        curWeight = 0;
        curValue = 0;
        heap = new PriorityQueue<>(Collections.reverseOrder());
        int maxp = bbKnapsack();
        return maxp;
    }

    // 真正执行递归的函数体
    private static void backtrack(int i) {
        if (i > n) {
            // 到达叶子节点
            bestValue = curValue;
            return;
        }

        // 搜索子树 进入左子树
        if (curWeight + weights[i] <= capacity) {
            btNum++;
            curWeight += weights[i];
            curValue += values[i];
            backtrack(i + 1);
            curWeight -= weights[i];
            curValue -= values[i];
        }

        // 进入右子树
        if (bound(i + 1) > bestValue) {
            btNum++;
            backtrack(i + 1);
        }
    }

    private static double bound(int i) {
        double cleft = capacity - curWeight; // 剩余容量
        double bound = curValue;

        // 以物品单位重量价值递减顺序装入物品
        while (i <= n && weights[i] <= cleft) {
            cleft -= weights[i];
            bound += values[i];
            i++;
        }

        // 装满背包
        if (i <= n) {
            bound += values[i] * ((double) cleft / weights[i]);
        }
        return bound;
    }

    // 打印输出数组
    private static void printArray(int[] arr) {
        int maxLen = 10; // 每行显示的最大元素个数
        System.out.print("[");
        for (int i = 1; i < arr.length; i++) {
            System.out.print(arr[i] + (i < arr.length - 1 ? " " : ""));
            if (i % maxLen == 0 && i != arr.length - 1) {
                System.out.println();
            }
        }
        System.out.print("]");
        System.out.println();
    }

    // 将一个新的活结点插入到子集树和最大堆H中
    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.offer(node);
    }

    // 优先队列式分支限界法，返回最大价值，bestx返回最优解
    private static int bbKnapsack() {
        // 初始化
        BBnode enode = null;
        int i = 1;
        double bestp = 0.0; // 当前最优值
        double up = bound(1); // 价值上界

        // 搜索子集空间树
        while (i != n + 1) {
            double wt = curWeight + weights[i];
            if (wt <= capacity) {
                if (curValue + values[i] > bestp) {
                    bestp = curValue + values[i];
                }
                addLiveNode(up, curValue + values[i], curWeight + weights[i], i + 1, enode, true);
            }
            up = bound(i + 1);

            if (up >= bestp) {
                addLiveNode(up, curValue, curWeight, i + 1, enode, false);
            }

            // 取下一扩展节点
            HeapNode node = heap.poll();
            enode = node.liveNode;
            curWeight = (int) node.weight;
            curValue = (int) node.profit;

            up = node.upperProfit;
            bbNum++;
            i = node.level;
        }

        //构造当前最优解
        for (int j = 0; j < n; j++) {
            bestx[q[j].id] = (enode.leftChild) ? 1 : 0;
            enode = enode.parent;
        }

        return curValue;
    }

    static class Element implements Comparable {
        int id;  //物品编号
        double unitVal;  //单位重量价值

        public Element(int id, double unitVal) {
            this.id = id;
            this.unitVal = unitVal;
        }

        @Override
        public int compareTo(Object o) {
            double od = ((Element) o).unitVal;
            return Double.compare(unitVal, od);
        }
    }

    static class BBnode {
        BBnode parent;  //父节点
        boolean leftChild;  //左儿子节点标志

        BBnode(BBnode par, boolean ch) {
            this.parent = par;
            this.leftChild = ch;
        }
    }

    static class HeapNode implements Comparable {

        BBnode liveNode;  //活结点
        double upperProfit;  //结点的价值上界
        double profit;
        double weight;
        int level;

        public HeapNode(BBnode liveNode, double upperProfit, double profit, double weight, int level) {
            this.liveNode = liveNode;
            this.upperProfit = upperProfit;
            this.profit = profit;
            this.weight = weight;
            this.level = level;
        }

        @Override
        public int compareTo(Object o) {
            double oup = ((HeapNode) o).upperProfit;
            return Double.compare(upperProfit, oup);
        }
    }
}