算法设计与分析(第五章).ppt

* 计算机算法设计与分析 * 用回溯法解0-1背包问题 Try(s){ for (i = 0; i 2; i++) { if (W+w[s]*i = C) { N[s] = i; W=W + w[s]*i; NV = NV + v[s]*i;} if (满足成功条件) {成功并输出结果} else Try(s+1); if (不成功) 删去next的记录; }} return 成功与否} s == n * 计算机算法设计与分析 * 用回溯法解0-1背包问题 Try(s){ 做挑选候选者的准备； while (未成功且还有候选者){ 挑选下一个候选者next； if (next可接受) { 记录next； if (满足成功条件) {成功并输出结果} else Try(s+1); if (不成功) 删去next的记录; }} return 成功与否} for (i = 0; i 2; i++) { (Accept(s) { Record(s) (s = = n) s = = n {if ( better ) TakeNewChoice( );} * 计算机算法设计与分析 * 用回溯法解0-1背包问题 Try(s){ 做挑选候选者的准备； while (未成功且还有候选者){ 挑选下一个候选者next； if (next可接受) { 记录next； if (满足成功条件) {成功并输出结果} else Try(s+1); if (不成功) 删去next的记录; }} return 成功与否} for (i = 0; i 2; i++) { (Accept(s) { Record(s) (s = = n) {if ( better ) TakeNewChoice( );} 这里无论成功与否都要继续考察 Move-off(s, i);} return } “记录”的逆操作 * 计算机算法设计与分析 * 用回溯法解0-1背包问题 Try(s){ for (i = 0; i 2; i++) if (Accept(i)) { Record(s, i)； if (s = = n) {if ( better ) TakeNewChoice( );} else Try(s+1); Move-off(s, i);} return } (NV V) 加上新物品未超过背包容量 新的价值超过原来的价值 * 计算机算法设计与分析 * 用回溯法解0-1背包问题 Try(s){ for (i = 0; i 2; i++) if (Accept(i)) { Record(s, i)； if (s = = n) {if ( better ) TakeNewChoice( );} else Try(s+1); Move-off(s, i);} return } (W+w[s]*i = C) { (NV V) * 计算机算法设计与分析 * 0-1背包问题中的几个子程序 Record(s, i){N[s] = i; W=W + w[s]*i; NV = NV + v[s]*i;} Move-off(s, i){N[s] = 0; W = W – w[s]*i; NV = NV – v[s]*i;} TakeNewChoice( ) { for (i=1; i=n; i++) { P[i] = N[i]; V = NV;}} * 计算机算法设计与分析 * 0-1背包问题的主程序 Bag(n, C, w[n], v[n]) { for (i=1; i=n; i++) {N[i]=0; P[i] = 0; T[i] = 1;} NV = 0, W = 0; V = 0; Try(1); Output(P); } * 计算机算法设计与分析 * 考虑0-1背包问题的迭代实现 先看看回溯法的一般的迭代形式： Backtr