第5章回溯法讲述.ppt

const int N=5;/*物品个数*/ int cv=0;/*当前价值*/ int cw=0;/*当前重量*/ int bestv=0;/*当前最优价值*/ int bestx[N+1];/*当前最优解*/ int C=10;/*背包容量*/ int v[N+1]={0,6,3,6,5,4},w[N+1]={0,2,2,4,6,5}; /*物品价值、重量。0元素不用*/ int x[N+1]={0}; //x[i]表示物品i当前是否加入背包 void main() { Backtrack(1); putout(); } void Backtrack(int i) //回溯求最优解 {int j; if(iN) /*到叶结点*/ { for (j=1;j=N;j++) bestx[j]=x[j]; bestv=cv; } else { if (cw+w[i]=C) /*有哪些信誉好的足球投注网站左子树*/ {x[i]=1; cw+=w[i]; cv+=v[i]; Backtrack(i+1); cw-=w[i]; cv-=v[i]; } if (Bound(i+1)bestv)/*有哪些信誉好的足球投注网站右子树*/ { x[i]=0; Backtrack(i+1); } } } void putout() {cout放入背包的物品是:; cw=0; for (int i=1;i=N;i++) if (bestx[i]==1) {couti\t; cw+=w[i];} coutendl放入背包物品总重为：cw\t; cout最大价值和为:bestvendl; } 0-1背包课件演示.cpp w[]={ ,2,2,4,6,5} ,N=5, C=10, v[]={ ,6,3,6,5,4} 0 Cr=C=10，V=0 1 w1=2,v1=6 Cr=8 ,cv=6 5 2 w2=2,v2=3 Cr=6,cv=9 Bound= 15bestp Bound=16 3 1:bestp=15 10 Bound= 12 4 w3=4,v3=6 Cr=2,cv=15 6 Cr=2,cv=15 7 Bound=15 Cr=2,cv=15 8 Bound=14bestp 9 5.3 练习-画出剪枝图 装载问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且 装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。 装载问题 可以证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。 (1)首先将第一艘轮船尽可能装满； (2)将剩余的集装箱装上第二艘轮船。 将第一艘轮船尽可能装满等价于选取全体集装箱的一个子集，使该子集中集装箱重量之和最接近C1。由此可知，装载问题等价于以下特殊的0-1背包问题。 用回溯法设计解装载问题的O(2n)计算时间算法。 装载问题 解空间：子集树 可行性约束函数(选择当前元素)： 上界函数(不选择当前元素)： 当前载重量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]; } 批处理作业调度 给定n个作业的集合{J1,J2,…,Jn}。每个作业必须先由机器1处理，然后由机器2处理。机器j处理作业Ji需要时间为ti