贪心算法习题解析

背包问题定义如下：输入：正数输出：，使得：最大；给出一个求解背包问题的贪心算法，并证明其正确性。解：贪心思想：首先计算每种物品单位重量的价值，并进行由大到小的排序，然后依据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包，若将这种物品全部装入背包后，背包内的物品总重量未超出，则选择单位重量价值次高的物品，以此类推，每次都是选择当前未放入背包的单位重量价值最高的物品，直到总重量大于或等于。优化子结构：设A是此背包问题的优化解，且A包含物品j，其中j的重量为w，则A’=A-{}是剩余的n-1个原重物品1,2,…,j-1,j+1,n以及重为的物品j中可装入容量为M-w的背包问题的优化解。证明：利用反证法。假设A’不是该子问题的优化解，则存在B’是该子问题的优化解，由此可知B'的价值大于A'的价值，令B=B'+{}，则B的价值大于A的价值，这与A是此问题的优化解相矛盾。所以此问题具有优化子结构。贪心选择性：计算每种物品单位重量的价值，并进行由大到小的排序。若，则存在背包问题的一个最优解使得。证明：设A是一个优化解，设其第一个物品的选择为(1)如果，则命题成立。(2)如果，则X1在全部放入背包总价值不会超过M的情况下，并没有全部放入，设B满足，(i=2,3,...,n)与A相同，且调整最终的价值不会超过M，则B是一个优化解且满足正确性证明：因为算法处理过程按照最有子结构和贪心选择性依次处理背包问题，则此算法具有正确性。2.写出分支界限的一般算法。（利用爬山算法）解：1)构造由根组成的单元素栈S，根节点的权值初始化为0；2)将可行解初始化为cost=；3)计算当前栈顶的权值=父节点的权值+该扩展分支的权值；4)IfTop(S)是目标节点then根据该节点计算当前可行解cost，cost=新的可行解；5)If当前栈顶Top(S)的cost’>cost，则Pop(S)，且不再将其子节点入栈；6)将S的子节点按照其启发式测度由大到小的顺序压入S；7)IfS空且cost=，then失败;8)IfS空且cost!=，returncost;9)Elsegoto3.3.是一个可能解，当且仅当必是一个拓扑序列。证明：=>是一个可能解，而每个人的工作能力符合关系，则对于，若满足偏序关系，则有；若不满足偏序关系，则的分配无所谓顺序，所以，必是一个拓扑序列；<=是一个拓扑序列，对于，若满足偏序关系，则有，其分配满足；若不满足偏序关系，则的分配无所谓顺序，不妨使得分配情况满足，于是将所有的工作分配完成之后，使得成立，则是一个分配任务的可能解。4.修改拓扑排序算法，写出严格的分支界限算法。（使用爬山法）解：1)生成树根root，其权值为解代价下界；2)将可行解的代价初始化为cost=；3)选择偏序集中没有前序元素的所有元素，根据加工后的代价矩阵元素，按权值由大到小依次入栈，作为root的子节点；4)Forroot的每个子节点v，其权值为加工后的代价矩阵元素加其父节点权值；5)如果此节点为目标节点，且权值不大于cost，则令cost=当前节点的权值，作为界限；6)如果此节点权值大于cost，则将此分支剪掉，其子节点不再入栈；7)S=S-{v};8)把v作为根，递归地处理S.5.给出求解旅行商问题的详细算法。解：1)根据各边之间的权值，列出此问题的初始代价矩阵；2)将代价矩阵进行处理，每行（列）减去减去该行(列)的最小值，使得每行(列)至少有一个零，其余各元素非负，每行（列）所减去所有数的和即为解的代价下界；3)选择满足下列条件的边(i,j)，使得，，所有包含(i,j)的解集合作为左子树，所有不包含(i,j)的解集合作为右子树；4)左子树的代价下界不变，计算右子树的代价：分别从变换后的代价矩阵的第i行第j列中找到具有最小代价的从i出发的边(i,k)和进入j边(r,j)，将这两条边的代价与其父节点的解的代价下界求和，即为右子树节点的代价下界；5)构造左子树根对应的代价矩阵：矩阵中的第i行第j列应该被删除，并且代价矩阵的(j,i)元素的位置应该被置为；6)计算左子树的代价下界：此时左子树的代价矩阵中可能出现某行或某列没有0的情况，则需相应的减去一个对应行或列的最小数，于是可以获得左子树的新代价下界；7)构造右子树根对应的代价矩阵：把代价矩阵的(j,i)元素的位置置为；8)计算右子树的代价下界：此时右子树的代价矩阵中可能出现某行或某列没有