问题描述

有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且image.png，装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。

问题分析

(1)首先将第一艘轮船尽可能装满；
(2)将剩余的集装箱装上第二艘轮船。
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近c1。由此可知，装载问题等价于以下特殊的0-1背包问题。
image.png
回溯法设计解装载问题的O(2n)计算时间算法。在某些情况下该算法优于动态规划算法O(nlogn)（主要计算量是对集装箱从小到大的排序）。
n**n>n!>2n,n3>n2**>nlogn>n>logn>1

算法思路

用树表示解空间,则解为n元向量{x1, … ,xn }, xi∈{0, 1} 。

约束条件：

可行性约束函数(选择当前元素)：
image.png
当前搜索的层i <= n时，当前扩展结点Z为子集树的内部结点，仅当满足cw+w[i] <= c时进入左子树，x[i]=1; 当cw+w[i] > c ，在以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中解都是不可行解，因而将在该子树删去。

限界函数：

上界函数(不选择当前元素):
当前载重量cw+剩余集装箱的重量r≤当前最优载重量bestw
在以Z为根的子树中任意叶结点所相应的载重量不超过cw + r。因此，当cw + r (限界函数) ≤ bestw时，可将Z的右子树剪去。即：cw + r > bestw 时搜索右子树，x[i]=0;

案例

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

核心代码中计算的时间复杂度为O(2n)

  1. void Backtrack(int i)   //搜索第i层结点
  2. {
  3.      if (i > n)//到达叶子节点
  4.     {
  5.         if (cw > bestw)//存在更优解
  6.         {
  7.             for (int j = 1; j <= n; ++j)
  8.                 bestx[j] = x[j];
  9.             bestw = cw;
  10.         }
  11.         return;
  12.     }
  13.     r -= w[i]; 
  14.     if (cw + w[i] <= c1)//搜索左子树
  15.     { 
  16.         x[i] = 1;
  17.         cw += w[i];
  18.         Backtrack(i + 1);
  19.         cw -= w[i];
  20.     }
  21.     if (cw + r > bestw)  //搜索右子树
  22.     {   
  23.         x[i] = 0;
  24.         Backtrack(i + 1);
  25.     }
  26.     r += w[i];
  27. }

为了构造最优解，必须在算法中记录与当前最优值相应的当前最优解，引入bestx数组，其中bestx数组可能被更新O(2n),故改进后算法时间复杂度为O(n2**n**)

#include <iostream>
using namespace std;

#define n 3         //集装箱数
#define c1 50       //第一艘轮船的载重量
#define c2 50       //第二艘轮船的载重量

int w[n + 1] = { 0, 10, 40, 40 };     //集装箱重量数组
//int w[n + 1] = { 0, 20, 40, 40 };    //测试数据(输出：不能装入)

int cw = 0;                     // 当前载重量, current weight
int x[n+1] = { 0, 0, 0, 0 };    //当前解,x[i]=1代表物品i装入第一个船，0代表不装入

int bestx[n+1]={ 0, 0, 0, 0 };  //存储最优解Init
int bestw = 0;                  //最优载重量

int r = 0;          //剩余集装箱重量（不包括已遍历但未装入的部分）

void backtrack(int i)// 搜索第i层结点
{
    if (i > n)
    {
        if (cw > bestw)//存在更优解
        {
            for (int j = 1; j <= n; ++j)
                bestx[j] = x[j];
            bestw = cw;
        }
        return;
    }
    r -= w[i];
    if (cw + w[i] <= c1) //约束条件,搜索左子树
    {
        cw += w[i];
        x[i] = 1;
        backtrack(i + 1);
        cw -= w[i];
    }
    if (cw + r > bestw) //限界函数,搜索右子树
    {   //当前载重量cw+剩余集装箱的重量r(不包括已遍历但未装入的部分)>当前最优载重量bestw
        //如果不满足直接剪枝，即当前载入量加所有剩余量小于最优值（无需考虑）
        x[i] = 0;
        backtrack(i + 1);
    }
    r += w[i];
}

void Print()
{
    int restweight = 0;//剩余货物重量
    for (int i = 1; i <= n; ++i)
        if (bestx[i] == 0)
            restweight += w[i];
    if (restweight > c2)
        cout << "不能装入" << endl;

    else{
        cout << "船1装入的货物为:";
        for (int i = 1; i <= n; ++i)
            if (bestx[i] == 1)
                cout << " " << i;

        cout << endl << "船2装入的货物为:";
        for (int i = 1; i <= n; ++i)
            if (bestx[i] != 1)
                cout << " " << i;
    }
}
int main()
{
    for (int i = 1; i <= n; ++i)
        r += w[i];
    backtrack(1);

    Print();
}

运行结果：
船1装入的货物为: 1 2
船2装入的货物为: 3