贪心算法的应用

贪心算法的应用课程名称： 算法设计与分析 院 系： 计算机科学与信息工程学院 学生姓名： * 学 号： * 专业班级：*指导教师： * 201312-27贪心算法的应用摘 要：顾 名 思 义 ， 贪 心 算 法 总 是 作 出 在 当 前 看 来 最 好 的 选 择 。 也 就 是 说贪 心 算 法 并 不 从 整 体 最 优 考 虑 ， 它 所 作 出 的 选 择 只 是 在 某 种 意 义 上 的 局 部 最优 选 择 。 当 然 ， 希 望 贪 心 算 法 得 到 的 最 终 结 果 也 是 整 体 最 优 的 。 虽 然 贪 心 算法 不 能 对 所 有 问 题 都 得 到 整 体 最 优 解 ， 但 对 许 多 问 题 它 能 产 生 整 体 最 优 解 。如 单 源 最 短 路 经 问 题 ， 最 小 生 成 树 问 题 等 。 在 一 些 情 况 下 ， 即 使 贪 心 算法 不 能 得 到 整 体 最 优 解 ， 其 最 终 结 果 却 是 最 优 解 的 很 好 近 似 。 贪 心 算 法 求 问题 一 般 具 有 两 个 重 要 性 质 ： 贪心选择性质和最优子结构性质。所 谓 贪 心 选 择性 是 指 所 求 问 题 的 整 体 最 优 解 可 以 通 过 一 系 列 局 部 最 优 解 的 选 择 ， 即 贪 心 选择 达到。这 是 贪 心 算 法 可 行 的 第 一 个 基 本 要 素 ， 也 是 贪 心 算 法 与 动 态 规 划 算 法 主要 区 别 。 当一个 问 题 的 最 优 解 包 含 其 子 问 题 的 最 优 解 时 ， 称 此 问 题 具 有 最 优子 结 构 性 质 。 问 题 的 最 优 子 结 构 性 质 是 该 问 题 可 用 动 态 规 划 算 法 或 贪 心 算 法求 解 的 关 键 特 征 。背包问题是一个经典的问题，我们可以采用多种算法去求解 0/1 背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。关键词：贪心法 背包问题 最优化 目 录第 1 章 绪论 .31.1 贪心算法的背景知识 .31.2 贪心算法的前景意义 .3第 2 章 贪心算法的理论知识 .42.1 问题的模式 .42.2 贪心算法的一般性描述 .4第 3 章 背包问题 .53.1 问题描述 .53.2 问题分析 .53.3 算法设计 .53.4 测试结果与分析 .10第 4 章 结论 .12参考文献 .13附件 .13第 1 章 绪论1.1 贪心算法的背景知识 贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。 “贪心”可以理解为以逐步的局部最优，达到最终的全局最优。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪心策略要有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的决策影响。也就是说某状态以后的过程不会影响以前的状态，至于当前的状态有关，也称这种特性为无后效性。已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。例如为了使生产某一产品所花费的时间最少，一种贪心的策略就是在生产该产品的每一道工序上都选择最省时的方法。所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。1.2 贪心算法的前景意义贪心算法的主要思想是从 问 题 的 某 一 个 初 始 解 出 发 逐 步 逼 近 给 定 的 目 标 ，以 尽 可 能 快 的 地 求 得 更 好 的 解 。 当 达 到 某 算 法 中 的 某 一 步 不 能 再 继 续 前 进 时算 法 停 止 。 该 算 法 存 在 问 题 其 一 是 不 能 保 证 求 得 的 最 后 解 是 最 佳 的 ； 其 二 ，不 能 用 来 求 最 大 或 最 小 解 问 题 ； 其 三 ， 只 能 求 满 足 某 些 约 束 条 件 的 可 行 解 的范 围 。 所 以 贪 心 算 法 是 解 决 最 优 化 问 题 时 的 一 种 简 单 但 适 用 范 围 有 限 的 策 略 。贪 心 算 法 无 后 向 性 在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。贪婪算法策略在数据结构课程中的算法也有广泛的应用，如霍夫曼树、构造最小生成树的 Prim 算法和 Kruskal 算法的决策过程，都是使用的贪婪算法策略。第 2 章 贪心算法的理论知识2.1 问题的模式对于背包问题。重量为 w1,w2,w3wn 的若干物品和容量为 m 的背包，物品的价值分别为p1,p2,p3pn。要求找出这 n 个物品的一个子集，使其尽可能是选入背包的物品的价值最大，即：最大化：w1+w2+w3+wnm 时，对物品先进行按单位价值高到低排序，为了不把物品原来的编码打乱，采用一个数组来存放单位价值从大到小的物品的编码即可。所以就只能选取 n 个货物中的一部分使其总利润最大。2.2 贪心算法的一般性描述 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题它能产生整体最优解或者是整体最优解的近似解。贪心算法的基本思路如下：（1）建立数学模型来描述问题。（2）把求解的问题分成若干个子问题。（3）对每一子问题求解，得到子问题的局部最优解。（4）把子问题的解局部最优解合成原来解问题的一个解。这就是一个用贪婪算法来解决背包问题课题，我们假设每一种货物都可以分成需要的任意小部分放入背包，要求从中取得最大利润。因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。第 3 章 背包问题3.1 问题描述贪心算法解决背包问题：一个商人带着一个能装 m 千克的背包去乡下收购货物，准备将这些货物卖到城里获利。现在有 n 种货源，且知道第 i 中货物有 wi千克，可获利 pi元。请编写算法帮助商人收购货物，以获取最高的利润。3.2 问题分析首先，输入物品的个数和背包的容量，再对所有物品的重量累加如果总重量小于背包的容量，就将所有的物品装入背包；如果大于背包的总容量将这些物品按照单位价值从高到低的顺序进行排序，然后进行选择。并且要求所选物品的最终总量不能超过背包能承受的重量，要求所选的最终方案为最优。3.3 算法设计对于本课题我们可一大致分两种情况：当 w1+w2+w3+.+wnm 的情况，只能选取一部分货物装入背包，这里假设每一个物品都可以分成任意一小部分，所以利用贪心策略，每次优先选取价值与重量比最大的装入背包，就能获得最高的利润，直到背包刚好装满为止，然后输出必要的数据及结果。在对物品按单位价值从大到小排列的具体实现可以使用快速排列算法，并用 p1max=0 来标记已经进行排列的物品，这样可以使搜索的项越来越少。3.3.1 算法分析因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：（1）先将单位块收益按从大到小进行排序；（2）初始化背包当前装入量和当前价值；（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，背包当前装入量加上物品总体积；b.如果可以部分放进，当前价值加上物品价值*背包剩余体积，以至于背包的剩余体积为 0.利用贪心策略解题，需要解决两个问题：（1）确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：a. 可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。b. 原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。（2）如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。3.3.2 数据结构在进行算法设计时为了使数据更容易观察和操作，我们需要设定一些必要的数组等变量。m 变量是背包的容量，n 是物品的总种类数，pp 是装入背包中物品的总价值。W 数组来存放输进来的物品的重量，其下标代表物品的编号；P 数组存放每一件物品的价值，同样下标代表物品的编号；P1 是 P 数组的副本是用来在计算中使用的，有可能会改变其中的值；b 数组用来存放根据单位价值由大到小排了序的物品的编号；它的下标代表着物品单位价值的大小的次序。比如：b1是单位价值最大的物品的编号。再定义一个计算装入背包中的物品的总价值，可以在输出结果时在输出选取物品的编码和