信息学竞赛必备算法系列
将第一艘船装至它的重量极限; 2) 将剩余货箱装到第二艘船。为了尽可能地将第一艘船
装满,需要选择一个货箱的子集,它们的总重量尽可能接近 c1。这个选择可通过求解 0 /
1 背包问题来实现,即寻找 m ax (n åi = 1wi xi ),其中 n åi = 1wi xi≤c1,xi Î{ 0 , 1
},1≤i≤n。当重量是整数时,可用 1 5 . 2 节的动态规划方法确定第一艘船的最佳装载。
用元组方法所需时间为 O ( m i n {c1 , 2 n })。可以使用回溯方法设计一个复杂性为 O
( 2n ) 的算法,在有些实例中,该方法比动态规划算法要好。
2. 第一种回溯算法
既然想要找到一个重量的子集,使子集之和尽量接近 c1,那么可以使用一个子集空间,
并将其组织成如图 1 6 - 2 那样的二叉树。可用深度优先的方法搜索该解空间以求得最优
解。使用限界函数去阻止不可能获得解答的节点的扩张。如果 Z 是树的 j+ 1 层的一个节
点,那么从根到 O 的路径定义了 xi(1≤i≤j)的值。使用这些值,定义 c w(当前重量)
为 n åi = 1wi xi 。若 c w>c1,则以 O 为根的子树不能产生一个可行的解答。可将这个
测试作为限界函数。当且仅当一个节点的 c w 值大于 c1 时,定义它是不可行的。
例 4-5 假定 n= 4,w= [ 8 , 6 , 2 , 3 ],c1 = 1 2。解空间树为图 1 6 - 2 的树再
加上一层节点。搜索从根 A 开始且 c w= 0。若移动到左孩子 B 则 c w= 8,c w≤c1 = 1
2。以 B 为根的子树包含一个可行的节点,故移动到节点 B。从节点 B 不能移动到节点
D,因为 c w+w2 >c1。移动到节点 E,这个移动未改变 c w。下一步为节点 J,c w= 1
0。J 的左孩子的 c w 值为 1 3,超出了 c1,故搜索不能移动到 J 的左孩子。
可移动到 J 的右孩子,它是一个叶节点。至此,已找到了一个子集,它的 c w= 1
0。xi 的值由从 A 到 J 的右孩子的路径获得,其值为[ 1 , 0 , 1 , 0 ]。
回溯算法接着回溯到 J,然后是 E。从 E,再次沿着树向下移动到节点 K,此时 c w=
8。移动到它的左子树,有 c w= 11。既然已到达了一个叶节点,就看是否 c w 的值大于
当前的最优 c w 值。结果确实大于最优值,所以这个叶节点表示了一个比[ 1 , 0 , 1 , 0 ]
更好的解决方案。到该节点的路径决定了 x 的值[ 1 , 0 , 0 , 1 ]。从该叶节点,回溯到节
点 K,现在移动到 K 的右孩子,一个具有 c w= 8 的叶节点。这个叶节点中没有比当前最
优 cw 值还好的 cw 值,所以回溯到 K , E , B 直到 A。从根节点开始,沿树继续向下移动。
算法将移动到 C 并搜索它的子树。
当使用前述的限界函数时,便产生了程序 1 6 - 1 所示的回溯算法。函数 M a x L o a
d i n g 返回≤c 的最大子集之和,但它不能找到产生该和的子集。后面将改进代码以便找
到这个子集。
M a x L o a d i n g 调用了一个递归函数 m a x L o a d i n g,它是类 L o a d i n g 的
一个成员,定义 L o a d i n g 类是为了减少 M a x L o a d i n g 中的参数个数。
maxLoading(1) 实际执行解空间的搜索。MaxLoading(i) 搜索以 i 层节点(该节点已被
隐式确定)为根的子树。从根到该节点的路径定义的子解答有一个重量值 c w,目前最优
解答的重量为 b e s t w,这些变量以及与类 L o a d i n g 的一个成员相关联的其他变量,
均由 M a x L o a d i n g 初始化。
程序 16-1 第一种回溯算法
template<class T>
class Loading {
friend MaxLoading(T [], T, int);
p r i v a t e :
void maxLoading(int i);
int n; // 货箱数目
T *w, // 货箱重量数组