Fork me on GitHub

货箱装载问题

发表于 | 分类于 | | 本文总阅读量 次
本文给出了货箱装载问题的两种情况，并对第二种情况给出了求解算法。

1. 装箱问题1

1.1. 问题描述

在装箱问题中，箱子的数量不限，每个箱子的容量为 binCapacity，待装箱的物品有 n 个，物品 i 需要占用的箱子容量为 $objectSize[i],0{\leq}objectSize[i]{\leq}binCapacity$。所谓 可行装载（feasible packing），是指所有物品都装入箱子而不溢出。所谓 最优装载（optimal packing） 是指使用箱子最少的可行装载。

1.2. 问题求解

近似算法：箱子装载问题和机器调度问题一样，是 NP-复杂问题，因此常用近似算法求解。求解所得的箱子树不是最少，但接近最少，有5中流行的近似算法：

  1. 最先适配法（First Fit, FF）：物品按 $1,2,3…,n$ 的顺序装箱。假设箱子从左到右排列，每一物品 i 放入可装载它的最左面的箱子。
  2. 最优适配法（Best Fit, BF）：令 $bin[j].unusedCapacity$ 为箱子 j 的可用容量。初始时，所有箱子的可用容量为 $binCapacity$。物品 i 放入可用容量 $unusedCapacity$ 最小但不小于 $object[i]$ 的箱子（此方法更能充分的利用空间）。
  3. 最先适配递减法（First Fit Decreasing, FFD）：此方法与 FF 类似，区别在于，所有物品首先按所需容量的递减次序排列，即对于 $1{\leq}i<n$，有 $objectSize[i]{\geq}objectSize[i+1]$。
  4. 最优适配递减法（Best Fit Decreasing，BFD）：此方法与 BF 类似，区别在于，所有物品首先按所需容量的递减的次序排列，即对于 $1{\leq}i<n$，有 $objectSize[i]{\geq}objectSize[i+1]$。
  5. 相邻适配法：为装载一件物品，首先在非空的箱子中循环搜索能够装载该物品的箱子，如果找不到这样的箱子，就启用一个空箱子。

定理：设 $I$ 为装在问题的任一实例，$b(I)$ 为最优装载所用的箱子数，FF 和 BF 所用的箱子数不会超过 $(17/10)b(I)+2$，而 FFD 和 BFD 所用的箱子数不会超过 $(11/9)b(I)+4$。

实例：假设有 4 件物品，所需容量分别为 $objectSize[1:4]=[3, 5, 2, 4]$，把他们放入容量均为 7 的箱子。

  1. 使用 FF 法：共用了三个箱子：物品 1 和 3 放入箱子 1；物品 2 放入箱子 2；物品 4 放入箱子 3.
  2. 使用 BF 法：只用了两个箱子：物品 1 和 4 放入箱子 1；物品 2 和 3 放入箱子 2.
  3. 如果使用 FFD 和 BFD 方法：物品按 2,4,1,3 排序，最后结果一样；物品 2 和 3 放入箱子 1，物品 1 和 4 放入箱子 2.

用最先适配法求解装箱问题：可用 赢者树 实现。具体参考《数据结构、算法与应用 C++语言描述》（第二版）书籍的第 13 章（竞赛树）第 13.5 节。
另一种用 二叉搜索树 实现的参考该书的第 14 章（搜索树）第 14.6.2 节。

2. 装箱问题2

2.1. 问题描述

有两艘船，$n$个货箱。第一艘船的载重重量是$c_1$，第二艘船的载重重量是$c_2$。$w_i$是货箱$i$的重量且${\sum}_{i=1}^{n}{w_i}{\leq}{c_1+c_2}$。希望确定是否有一种方法可以把$n$个货箱全部装上船。如果有，找出这种方法。

扩展：当${\sum}_{i=1}^{n}{w_i}={c_1+c_2}$时，两艘船的装载问题等价于 子集之和（sum-of-subset） 问题，即有$n$个数字，要求找到一个子集（如果存在的话），使它的和为$c_1$。当$c_1=c_2$且${\sum}_{i=1}^{n}{w_i}={2c_1}$时，两艘船的装载问题等价于 分割问题（partition problem），即有$n$个数字$a_i(1{\leq}i{\leq}n)$，要求找到一个子集（如果存在的话），使得子集之和为$({\sum}_{i=1}^{n}{a_i}){/2}$。

2.2. 问题分析

只要有一种可行的方案，就可以验证以下的装船策略行之有效：

  1. 尽可能将第一艘船装载到它的装载极限；
  2. 将剩余货箱装到第二艘船。

为了尽可能地将第一艘船装满，需要选择一个货箱的子集，它们的总重量尽可能接近于$c_1$，这个选择可通过0/1背包问题解决：

$${\max}{\sum}_{i=1}^{n}{w_i x_i}$$

限制条件是

$${\sum}_{i=1}^{n}{w_i x_i}{\leq}{c_i}{\;\;\;}{x_i}{\in}{0,1},1{\leq}i{\leq}n$$

可以使用动态规划法确定第一艘船的最佳装载。这里使用回溯法设计一个复杂度为$O(2^n)$的算法。

构建解空间树表示，以3个货箱的装箱问题为例，树形表示如下：

1
2
3
4
5
6
7
           A
      /         \ 
     B           C
   /   \       /   \
  D     E     F     G
 / \   / \   / \   / \
H   I J   K L   M N   O

每个非叶子节点左子树表示1，右子树表示0。从$A$到$I$表示一种装箱策略，为$(1,1,0)$，即将第一和第二两个货箱装入第一艘船中。采用深度优先遍历该树即可得到货物装箱的所有可行解以及最优解。

可以看到，有些节点右子树不可能包含比当前最优解更好的解，则不需要移动到这种右子树中去。令$Z$为解空间树的第$i$层的一个节点。以$Z$为根的子树中没有叶节点的重量超过 weightOfCurrentLoading + remainingWeight（这两个变量的含义见代码1.3.1. 装载问题的回溯算法），其中remainingWeight = ${\sum}_{j=i+1}^{n}$weight[j]为剩余货箱的重量（$n$是货箱的数量）。因此，当
weightOfCurrentLoading + remainingWeight ${\leq}$ maxWeightSoFar
没有必要搜索$Z$的右子树

实现代码为1.3.1. 装载问题的回溯算法。

确定第一艘船的最佳装载后，判断剩余货物的总重量是否不大于第二艘船的载重重量$c_2$，如果是，则找到一个可行装载。

2.3. 问题求解

2.3.1. 装载问题的回溯算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
 * 装载问题求解
 */

#include <iostream>
#include <vector>
using namespace std;

/*
 * 问题描述：有两艘船，n个货箱。第一艘船的载重重量是c1，第二艘船的载重重量是c2。wi是货箱i的重量且 w1+w2+...+wn<=c1+c2。
 * 希望确定是否有一种方法可以把n个货箱全部装上船。如果有，找出这种方法。
 * 求解分析：只要有一种可行的方案，就可以验证以下装船策略有效：1.尽可能将第一艘船装载到它的载重量极限；
 * 2.将剩余货箱装载到第二艘船。为了尽可能地将第一艘船装满，需要选择一个货箱子集，它们的总重量尽可能接近于c1。
 * 这个选择可以通过01背包问题解决。
 * 求解策略：回溯法。
 */
int numberOfContainers;             // 货箱的数量
int capacity;                       // 船的载重量，即c1
int weightOfCurrentLoading;         // 当前装载的重量
int maxWeightSoFar;                 // 目前为止最大的载重量
int remainingWeight;                // 剩余货箱的重量
vector<int> weight;                 // 货箱重量
vector<int> currentLoading;         // 当前装载的策略，元素是0或者1，分别表示不转载和装载
vector<int> bestLoadingSoFar;       // 目前为止最优的装载策略，元素是0或者1.

void rLoad(int currentLevel){
    // 从currentLevel处的节点开始搜索
    if (currentLevel >= numberOfContainers){
        // 到达一个叶节点，存储更优的解
        for (int j = 0; j < numberOfContainers; ++j)
            bestLoadingSoFar[j] = currentLoading[j];
        maxWeightSoFar = weightOfCurrentLoading;
        return;
    }

    // 没有到达一个叶节点，检查子树
    remainingWeight -= weight[currentLevel];
    if (weightOfCurrentLoading + weight[currentLevel] <= capacity){
        // 搜索左子树
        currentLoading[currentLevel] = 1;
        weightOfCurrentLoading += weight[currentLevel];
        rLoad(currentLevel + 1);
        weightOfCurrentLoading -= weight[currentLevel];
    }
    // 因为当weightOfCurrentLoading + remainingWeight <= maxWeightSoFar时，
    // 即使搜索右子树也不会达到比maxWeightSoFar更好的结果，所以没有必要搜索右子树
    if (weightOfCurrentLoading + remainingWeight > maxWeightSoFar){
        currentLoading[currentLevel] = 0;           // 搜索右子树
        rLoad(currentLevel + 1);
    }
    remainingWeight += weight[currentLevel];
}

int main(int argc, char** argv){
    // 初始化全局变量
    int theWeight[] = {5, 10, 15, 20, 25};
    numberOfContainers = sizeof(theWeight)/sizeof(int);
    capacity = 40;
    weightOfCurrentLoading = 0;
    maxWeightSoFar = 0;
    remainingWeight = 0;
    weight.assign(theWeight, theWeight + numberOfContainers);
    currentLoading = vector<int>(numberOfContainers);
    bestLoadingSoFar = vector<int>(numberOfContainers);
    for (int i = 0; i < numberOfContainers; ++i)
        remainingWeight += weight[i];

    rLoad(0);       // 搜索策略树

    for (int i = 0; i < numberOfContainers; ++i)    // 输出最优装载策略
        cout << bestLoadingSoFar[i] << ' ';
    cout << endl;
    return 1;
}

代码输出结果：

1
1 1 0 0 1

2.3.2. 装载问题的迭代算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
/*
 * 装载问题求解
 */

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
ostream& operator<<(ostream& out, vector<T> vec){
    for (int i = 0; i < vec.size(); ++i)
        out << vec[i] << ' ';
    return out;
}

int maxLoading(vector<int>& weight, int numberOfContainers, int capacity, vector<int>& bestLoading){
    int weightOfCurrentLoading = 0;                                 // 当前装载的重量
    int maxWeightSoFar = 0;                                         // 目前为止最大的载重量
    int remainingWeight = 0;                                        // 剩余货箱的重量
    vector<int> currentLoading(numberOfContainers);                 // 当前装载的策略，元素是0或者1，分别表示不转载和装载
    for (int i = 0; i < numberOfContainers; ++i)
        remainingWeight += weight[i];
    
    // 对树进行搜索
    int currentLevel = 0;
    while (true){
        // 尽可能沿左分支移动
        while (currentLevel < numberOfContainers && 
        weightOfCurrentLoading + weight[currentLevel] <= capacity){
            // 移到左孩子
            remainingWeight -= weight[currentLevel];
            weightOfCurrentLoading += weight[currentLevel];
            currentLoading[currentLevel] = 1;
            ++currentLevel;
        }
        if (currentLevel >= numberOfContainers){
            // 到达叶节点
            for (int j = 0; j < numberOfContainers; ++j)
                bestLoading[j] = currentLoading[j];
            maxWeightSoFar = weightOfCurrentLoading;
        } else {
            // 移到右孩子
            remainingWeight -= weight[currentLevel];
            currentLoading[currentLevel] = 0;
            ++currentLevel;
        }
        // 需要时回溯
        while (weightOfCurrentLoading + remainingWeight <= maxWeightSoFar){
            // 这颗子树没有更好的叶节点，回溯
            --currentLevel;
            while (currentLevel > 0 && currentLoading[currentLevel] == 0){
                // 从一个右孩子回溯
                remainingWeight += weight[currentLevel];
                --currentLevel;
            }
            if (currentLevel == 0)
                return maxWeightSoFar;
            // 移到右子树
            currentLoading[currentLevel] = 0;
            weightOfCurrentLoading -= weight[currentLevel];
            ++currentLevel;
        }
    }
}

int main(int argc, char** argv){
    int theWeight[] = {5, 10, 15, 20, 25};
    int numberOfContainers = sizeof(theWeight)/sizeof(int);         // 货箱的数量
    int capacity = 40;                                              // 船的载重量，即c1
    vector<int> weight(theWeight, theWeight + numberOfContainers);  // 货箱重量
    vector<int> bestLoadingSoFar(numberOfContainers);               // 目前为止最优的装载策略，元素是0或者1.

    maxLoading(weight, numberOfContainers, capacity, bestLoadingSoFar);

    cout << bestLoadingSoFar << endl;
    return 1;
}

代码输出结果：

1
1 1 0 0 1