清华大学出版社 装载问题 RSITY PRESS 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其 中集装箱i的重量为wi,且∑w≤c+c2 装载问题要求确定是否有一个合理的装载方案可将这个集装箱 装上这2艘轮船。如果有,找出一种装载方案。 容易证明,如果一个给定装载问题有解,则采用下面的策略可 得到最优装载方案。 (1)首先将第一艘轮船尽可能装满 (2)将剩余的集裝箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集, 使该子集中集装箱重量之和最接近。由此可知,装载问题等价 于以下特殊的0-1背包问题。 maⅹ>v;x 用回溯法设计解裝载问题的O(2)计 算时间算法。在某些情况下该算法 t.>wx,≤c1 优于动态规划算法。 x∈{0l},1≤i≤n9 装载问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其 中集装箱i的重量为wi，且 1 2 1 w c c n i  i  + = 装载问题要求确定是否有一个合理的装载方案可将这个集装箱 装上这2艘轮船。如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略可 得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集， 使该子集中集装箱重量之和最接近。由此可知，装载问题等价 于以下特殊的0-1背包问题。 x i n w x c w x i n i i i n i i i       = = {0,1},1 s.t. max 1 1 1 用回溯法设计解装载问题的O(2n )计 算时间算法。在某些情况下该算法 优于动态规划算法