第5章 回溯法(1-例子).pdfVIP

装载问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其 中集装箱i的重量为wi，且 n w c c   i 1 2 i 1 装载问题是否有一个合理的装载方案可将这个集装箱装上这2艘 轮船？如果有，找出一种装载方案。 容易证明，如果一个给定装载问题有解，则采用下面的策略可 得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集， 使该子集中集装箱重量之和最接近c1。由此可知，装载问题等 价于以下特殊的0-1背包问题。 n max w x i i i 1 n 用回溯法设计解装载问题的O(2 )计 ws.t.x n c  算时间算法。 i i 1 i 1 1  {x0,1},1 i n i 装载问题 •解空间：子集树 n w x c  •可行性约束函数(选择当前元素)： i i 1 •上界函数(不选择当前元素)： i 1 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw void backtrack (int i) {// 有哪些信誉好的足球投注网站第i层结点 if (i n) { // 到达叶结点 更新最优解bestx,bestw; return;} r -= w[i]; if (cw + w[i] = c) {// 有哪些信誉好的足球投注网站左子树 x[i] = 1; cw += w[i]; backtrack(i + 1); cw -= w[i]; } if (cw + r bestw) {// 有哪些信誉好的足球投注网站右子树 x[i] = 0; backtrack(i + 1); } r += w[i]; 2 } 装载问题 • 构造最优解 P147 需在有哪些信誉好的足球投注网站过程中记录与当前最优装载重量值相匹配 的当前装载方案向量解(即当前最优解)。增加两个 量：x和bestx x用于记录从根到当前结点的路径 bestx用于记录当前最优解 3 0-1背包问题 • 解空间：子集树 n w x c  • 可行性约束函数：i i 1 • 上界函数： i 1 templateclass Typew, class Typep Typep KnapTypew, Typep::Bound (int