八皇后的递归算法 贪心法 void queen(int)【 问题的状态空间很大时,穷举法 for (=0; j<n; j++) if( place(L)【∥能放置吗 计算量可能会太大 X[= mark(4j);∥标记(lj)的影响 ●当人们面对一个问题时,可能会 f(<n-1) +1);∥接着试 采取目前看来最接近解状态的选 择方案 ●贪心法可以看作回溯的特例 贪心法的过程 部分装入背包问题 套搜索解的过程中,从根结点开 点中权值最关的为B,则选择作 一个旅行者准备随身携带一个背包。可以放 下一个结点 背包的物品有n个,每个物品的重量和价值 可以贪心解的问题需要满足的性质 分别为w,vj1,2…m,旅行者可以选择物 品的全部,也可以选择的x部分,0≤X≤1 ●贪心选择性质 如果背包的重量限制是c,怎么选择放入背包 最优子结构性质 的物品以使得背包的价值最大? ●时间代价多为线性 背包问题的形式定义 贪心法求解背包问题/ ·输入:c>0,w>0,v>0,=1…,n ·输出:<x1,x2,…,x> ●按照单位重量的价值从高到低对物 品排序 0≤x1≤1i=1 尽量装入“价值/重量”比最高的物 目标函数ma∑vx 品 直到不能装入一个整物品为止 约束条件 ●最后根据背包重量极限装入部分物品8 八皇后的递归算法 void queen(int i) { int j; for (j=0; j<n; j++) { if (place(i,j)) { // 能放置吗 X[i] = j; mark(i,j); // 标记（i,j）的影响 if (i < n-1) queen(i+1); // 接着试下一个 else print(count); // 打印一个解 erase(i,j); // 回溯，去掉刚才标记 } } } 贪心法 z问题的状态空间很大时，穷举法 计算量可能会太大 z当人们面对一个问题时，可能会 采取目前看来最接近解状态的选 择方案 z贪心法可以看作回溯的特例 贪心法的过程 z 在搜索解的过程中，从根结点开 始，设当前结点为A，A的所有子结 点中权值最大的为B，则选择B作为 下一个结点 z 可以贪心解的问题需要满足的性质 z 贪心选择性质 z 最优子结构性质 z 时间代价多为线性 部分装入背包问题 一个旅行者准备随身携带一个背包。可以放 入背包的物品有n个，每个物品的重量和价值 分别为wj ，vj ，j=1,2,…,n，旅行者可以选择物 品i的全部，也可以选择i的xi 部分，0≤xi ≤1。 如果背包的重量限制是c，怎么选择放入背包 的物品以使得背包的价值最大？ 背包问题的形式定义 z 输入：c>0, wi >0, vi >0, i=1,…, n z 输出：<x1, x2, …, xn> 目标函数 约束条件 ∑= n i i i v x 1 max ∑= ≤ n i i i w x c 1 0 ≤ xi ≤ 1 i = 1,2,..., n 贪心法求解背包问题 z 按照单位重量的价值从高到低对物 品排序 z 尽量装入 “价值/重量”比最高的物 品 z 直到不能装入一个整物品为止 z 最后根据背包重量极限装入部分物品