装载问题 RSTY PRESS 解空间:子集树 可行性约束函数(选择当前元素):∑mx≤c1 上界函数(不选择当前元素): 当前载重量cw剩余集装箱的重量r≤当前最优载重量 best private static void backtrack(int i) {∥/搜索第层结点 if(i>n)∥/到达叶结点 更新最优解 best, best; return r-=WO if(cW+w]<=c){/搜索左子树 刈=1; CW+= WO backtrack(i+ 1) cW-=W0]; 1 if (cw +r> best)i 刈]=0;∥搜索右子树 backtrack (i+1): y +=W10 装载问题 •解空间：子集树 •可行性约束函数(选择当前元素)： •上界函数(不选择当前元素)： 当前载重量cw+剩余集装箱的重量r当前最优载重量bestw 1 1 w x c n i  i i  = private static 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]; }