回溯算法求解轮船装载问题

Question

【问题描述】

 给定n个货箱,货箱i 重为 wi， 船可以装载的货箱总重量为 W。 货箱装载问题是在不超过载重量的前提下装载尽可能重的货箱。

装载问题的解可以用向量 (x1,x2,…,xn)表示，xi∈{0,1}, xi =1 表示货箱i被装上船， xi =0表示货箱 i不装上船。请设计一个基于回溯算法的装载问题的求解方案。

【输入】

第1行输入正整数n和船的装载重量W，第2行依次输入n个整数，表示n个货箱的重量。

【输出】

输出两行，第1行输出最大的装载重量，第2行输出解向量 (x1,x2,…,xn)。

【输入样例】

6 26

1 7 4 20 9 11

【输出样例】

25

1 0 1 1 0 0 

Answer 1

static int[] x = new int[w.length];
static int[] bestx = new int[w.length];
static int bestw = Integer.MIN_VALUE;
static int cw = 0;
static int r = 0; // 记录物品i后面所有物品的总重量

public static void main(String[] args) {
    for (int i = 0; i < w.length; i++) {
        r += w[i];
    }
    backstrace(0);

    int sum = 0;
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 0){
            sum += w[i];
        }
    }
    if(sum > c2){
        System.out.println("物品无法装载到轮船!");
        return;
    }

    System.out.println("C1:" + c1 + "装载物品:");
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 1){
            System.out.print(w[i] + " ");
        }
    }
    System.out.println();

    System.out.println("C2:" + c2 + "装载物品:");
    for (int i = 0; i < bestx.length; i++) {
        if(bestx[i] == 0){
            System.out.print(w[i] + " ");
        }
    }
    System.out.println();
}

private static void backstrace(int i) {
    if(i == w.length){
        if(cw > bestw){
            bestw = cw;
            for (int j = 0; j < x.length; j++) {
                bestx[j] = x[j];
            }
        }
    } else {
        r -= w[i];
        if(cw + w[i] <= c1){
            cw += w[i];
            x[i] = 1;
            backstrace(i+1);  // 选择第i个节点
            cw -= w[i];
        }

        if(cw + r > bestw){
            x[i] = 0;      // 才有必要去往右边的i节点
            backstrace(i+1); // 没选择第i个节点
        }

        r += w[i];
    }
}
运行结果：