先来看装载问题问题背景描述
装载问题可用动态规划解决，但回溯法有时能取得更好的效果
(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，遍历结束
网友评论