装载问题

装载问题
有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，集装箱总重量小于等于c1+c2,要求定一个合理的装载方案可将这n个集装箱装上这两艘轮船。

可以证明，如果一个给定装载问题有解，则采用下面的策略可得到最优的装载方案：

1）首先将第一艘轮船尽可能装满

2）将剩余的集装箱装上第二艘轮船

?

将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和接近第一艘轮船载重量c1.

该问题类似于0-1背包问题，可以用动态规划法解决。

?

用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。

?

回溯法实现：

?
?
?