装载问题
装载问题
有一批共n个集装箱要装上两艘载重量分别为c1和c2的轮船，集装箱总重量小于等于c1+c2,要求定一个合理的装载方案可将这n个集装箱装上这两艘轮船。
可以证明，如果一个给定装载问题有解，则采用下面的策略可得到最优的装载方案：
1）首先将第一艘轮船尽可能装满
2）将剩余的集装箱装上第二艘轮船
?
将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和接近第一艘轮船载重量c1.
该问题类似于0-1背包问题，可以用动态规划法解决。
?
用回溯法解装载问题时，用子集树表示其解空间显然是最合适的。
?
回溯法实现：
??
?
