装载问题 ——回溯法（Java）

1、 问题描述

有一批共n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集
装箱i的重量为Wi，且

$$\sum_{i=1}^{n} w_i <= C1 + C2$$

例如，当n=3,c1=c2=50,且w=[10,40,40]时，可将集装箱1和集装箱2装上一艘轮船，而将集装箱3装在第二艘轮船；如果w=[20,40,40],则无法将这3个集装箱都装上轮船。

1.1 装载问题

装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。

例如：

6个元素的数组{30,30,30,50,50,60}，容量 C1=100，C2=150.箱子总重量为250，轮船的总容量也为250，如何安排该装载？

• 如果使用贪心算法（按照重量从小到大），会先把30,30,30装到第一艘船，就造成了，10个空间的浪费，导致会有一个箱子不能装上船。

• 如果使用贪心算法（按照装载量尽量最大），会装50+50=100，然后30+30+30+60=150
  回溯法因为考虑到了所有的装载顺序，所以一定能找到最优的装载方案。

容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

(1)首先将第一艘轮船尽可能装满；

(2)将剩余的集装箱装上第二艘轮船。

1.2 转换问题

• 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近第一艘轮船的载重量。

• 由此可知，装载问题等价于以下特殊的0-1背包问题。

$$max\sum_{i=1}^{n} w_ix_i$$

$$\sum_{i=1}^{n} w_ix_i \leq C1, x_i \in \{ 0,1 \}, 1 \leq i \leq n$$

用回溯法设计解装载问题的O(2ⁿ)计算时间算法。在某些情况下该算法优于动态规划算法。

2、算法设计

2.1 可行性约束函数

$$\sum_{i=1}^{n} w_ix_i \leq C1$$

在子集树的第j+1层的节点Z处，用cw记当前的装载重量，即cw=(w1x1+w2x2+…+wjxj)，当cw>c1时，以节点Z为根的子树中所有节点都不满足约束条件，因而该子树中解均为不可行解，故可将该子树剪去。（该约束函数去除不可行解，得到所有可行解）

2.2 上界函数

• 设Z是解空间树第i层上的当前扩展结点。cw是当前载重量；bestw是当前最优载重量；r是剩余集装箱的重量，即

$$r=\sum_{j=i+1}^{n} w_j$$

• 定义上界函数为cw+r。在以Z为根的子树中任一叶结点所相应的载重量均不超过cw+r。因此，当cw+r<=bestw时，可将z的右子树剪去。

当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw

2.3 解空间树

核心代码

public static void backtrack(int t) {
if(t>n) {//到达叶结点
if(cw>bestw) 
bestw = cw;
return;
}
if(cw + w[i] <= c) {   //搜索左子树
cw += w[i]; //更新装载量
backtrack(i+1);
cw -= w[i];    //回溯到父结点，将装载量还原
}
backtrack(i+1);
}

2.4 剪枝函数

• 约束条件剪去”不可行解”的子树

• 上界条件剪去不含最优解的子树,r为剩余集装箱重量 $r=\sum_{j=i+1}^{n} w_j$，
  当前装载与r之和为右子树上界

保证算法搜索到的每个叶结点都是迄今为止找到的最优解

2.5 算法设计

• 先考虑装载一艘轮船的情况，依次讨论每个集装箱的装载情况，共分为两种，要么装(1)，要么不装(0)，因此很明显其解空间树可以用子集树来表示。

• 在算法maxLoading中，返回不超过c的最大子集和。

• 在算法maxLoading中，调用递归函数backtrack(1)实现回溯搜索。backtrack(i)搜索子集树中的第i层子树。

• 在算法backtrack中，当i>n时，算法搜索到叶结点，其相应的载重量为cw，如果cw>bestw，则表示当前解优于当前的最优解，此时应该更新bestw。

• 算法backtrack动态地生成问题的解空间树。在每个结点处算法花费O(1)时间。子集树中结点个数为O(2ⁿ)，故backtrack所需的时间为O(2ⁿ)。另外backtrack还需要额外的O(n)的递归栈空间。

为了构造最优解，需要记录与当前最优值相应的当前最优解。x用于记录从根至当前结点的路径，bestx记录当前最优解。在叶结点处进行修正。

//回溯算法
public static void backtrack(int t) {
  if(t>n) {//到达叶结点
    if(cw>bestw) {
      for(int i=1;i<=n;i++) {
        bestx[i] = x[i];
      }
      bestw = cw;
    }
  return;
  }
  r -= w[t];  //当前结点作为扩展结点，求子树剩余集装箱重量
  if(cw + w[t] <= c) {   //搜索左子树
    x[t] = 1;
    cw += w[t];
    backtrack(t+1);
    cw -= w[t];    //回溯到父结点
  }
  if(cw + r>bestw) { //根据限界函数
    x[t] = 0;    //搜索右子树
    backtrack(t+1);
  }
  r += w[t];//恢复现场
}

3、程序代码

public class Solution {

    // 类数据成员
    static int N;                   // 集装箱数量 - 1
    static int[] weight;            // 集装箱重量数组
    static int[] shipContain;       // 第一艘轮船的载重量
    static int currWeight;          // 当前载重量
    static int bestWeight;          // 当前最优载重量
    static int remain;              // 剩余集装箱重量
    static int[] solution;          // 当前解
    static int[] best;              // 当前最优解，best[i]表示第i+1个集装箱装载到第best[i]+1艘轮船时最优

    public static void main(String[] args) {
        // TODO 箱子|轮船总容量都为250
        weight = new int[]{30, 30, 30, 50, 50, 60};     // 每个集装箱重量
        shipContain = new int[]{100, 150};             // 两艘轮船的载重量分别为C1，C2

        // TODO 初始化类数据成员
        N = weight.length - 1;
        solution = new int[N + 1];
        best = new int[N + 1];
        currWeight = 0;
        bestWeight = 0;
        // TODO 初始化remain
        for (int i = 1; i <= N; i++) {
            remain += weight[i];
        }

        System.out.println("最优载重量为：" + maxLoading(weight, shipContain[0], best));

        System.out.println("最优装载数组：");
        for (int i = 0; i < best.length; i++) {
            if (i != best.length - 1) {
                System.out.print(best[i] + " ");
            } else {
                System.out.println(best[i]);
            }
        }

        int shipCnt = shipContain.length;
        int w = 0;

        for (int i = 1; i <= shipCnt; i++) {
            System.out.print("第" + i + "艘轮船装载的集装箱分别是：第");
            for (int j = 0; j <= N; j++) {
                if (best[j] == i - 1) {
                    System.out.print(j + 1 + ",");
                }
            }
            System.out.println("个");
        }

    }


    public static int maxLoading(int[] weight, int c1, int[] best) {
        // TODO 计算最优载重量
        backtrack(1, c1);
        return bestWeight;
    }

    private static void backtrack(int level, int c1) {
        // TODO 搜素第level层节点
        if (level > N) {
            // TODO 到达叶节点
            if (currWeight > bestWeight) {
                for (int i = 1; i <= N; i++) {
                    best[i] = solution[i];
                }
                bestWeight = currWeight;
            }
            return;
        }
        // TODO 搜索子树
        remain -= weight[level];
        if (currWeight + weight[level] <= c1) {
            // TODO 搜索左子树，即x[level] = 1
            solution[level] = 1;
            currWeight += weight[level];
            backtrack(level + 1, c1);
            currWeight -= weight[level];
        }
        if (currWeight + remain > bestWeight) {
            solution[level] = 0;
            backtrack(level + 1, c1);   // TODO 搜素右子树
        }
        remain += weight[level];
    }

    public static int maxLoading1(int[] w, int c, int[] bestx) {
        // TODO 迭代回溯法
        //  返回最优载重量及其相应解
        //  初始化根结点
        int curr = 1;
//        int n = w.length - 1;
        solution = new int[N];
//        bestWeight = 0;
//        currWeight = 0;
//        remain = 0;

        for (int j = 1; j <= N; j++) {
            remain += w[j];
        }
        // TODO 搜索子树
        while (true) {
            while (curr <= N && currWeight + w[curr] <= c) {
                // TODO 进入左子树
                remain -= w[curr];
                currWeight += w[curr];
                solution[curr] = 1;
                curr++;
            }
            if (curr > N) {
                // TODO 到达叶节点
                for (int i = 1; i <= N; i++) {
                    bestx[i] = solution[i];
                }
                bestWeight = currWeight;
            } else {
                // TODO 进入右子树
                remain -= w[curr];
                solution[curr] = 0;
                curr++;
            }
            while (currWeight + remain <= bestWeight) {
                // TODO 剪枝回溯
                curr--;
                while (curr > 0 && solution[curr] == 0) {
                    // 从右子树返回
                    remain += w[curr];
                    curr--;
                }
                if (curr == 0) {
                    return bestWeight;
                }
                // TODO 进入右子树
                solution[curr] = 0;
                currWeight -= w[curr];
                curr++;
            }
        }
    }

}

运行结果

4、参考资料

• 算法设计与分析（第四版）

结束！