回溯法之装载问题

先来看装载问题问题背景描述

装载问题可用动态规划解决，但回溯法有时能取得更好的效果

(1)First

ship the first ship as much as possible;

(2)The

remaining containers are loaded on the second ships.

先来装一个容积，先来装一条船

w是货物重量，c是容积大小

先装载一个容积是30的船

用子集树表示其解空间，用可行性约束函数可剪去不满足条件的子树

子集树解空间

cw记当前的装载重量，当cw > c1时，以结点Z为根的子树中所有结点都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪去；

找bestw的步骤

cw：当前重量

bestw:最优重量

r:剩余重量

如下图，总重量是46，在第一个物品（重16那个）看来，剩余r是30，然后下一步选取第一个物品，cw=16,此时，在第二个物品看来r就是15了，然后由于c=30,不能再选了，于是往右子树走了第三和第四步

走完之后回退

首先将原来的bestw从0改为16，然后判断r是否大于bestw,显然30>16,所以进入右子树

重复上边那张图的步骤

最后同样修改bestw,从16改为30，遍历结束