利用贪婪算法实现多种实际问题.doc

利用贪婪法实现多种实际问题 I 算法设计与分析 课程设计任务书 学院名称 数学与计算机学院 专业 信息与计算科学专业 年级 2007 一 设计题目 题目十四 利用贪婪算法实现多种实际问题 二 主要内容 给出多种可以用贪婪算法解决的典型问题 并分析 证明 编程 三 具体要求 1 贪婪算法的基本思想 2 给出背包问题的贪婪算法 3 给出有限期计算机作业调度的贪婪算法 4 给出上面两个算法的证明 5 给出上面两个算法的程序 6 给出时间复杂度 四 主要技术路线提示 在用贪婪算法解决资源分配问题 布线问题 0 1 背包问题过程中 使用贪婪算法解决问题 通常需要做好以下几个方面的工作 1 明确问题的求解目标 2 分析问题所包含的约束条件 3 建立优化函数 优化函数通常可以通过综合分析问题的求解目标及约束条件归纳出来 4 制定贪婪准则 五 进度安排 1 第一周 分析题目的需求 设计抽象数据类型 构思算法 通过类的设计实现抽象数据类型 并编写上机程序 2 第二周 完成程序开发 进行测试并分析结果 最后撰写课程设计报告 利用贪婪法解决实际问题 II 六 完成后应上交的材料 上交的成果的内容必须由以下四个部分组成 缺一不可 1 上交源程序 学生按照课程设计的具体要求所开发的所有源程序 应该放到一个文件夹中 2 上交程序的说明文件 保存在 txt 中 在说明文档中应该写明上交程序所在的目录 上 交程序的主程序文件名 如果需要安装 要有程序的安装使用说明 3 课程设计报告电子文档 保存在 word 文档中 文件名要求 按照 学号姓名算法分析课 设报告 doc 起名 如文件名为 200300109 张三算法分析课设报告 doc 按照课程设计的具体 要求建立的功能模块 每个模块要求按照如下几个内容认真完成 其中包括 1 需求分析 在该部分中叙述每个模块的功能要求等 2 概要设计 在此说明每个部分的算法设计说明 可以是描述算法的流程图 每个程序中使用的存储结构 设计说明 如果指定存储结构请写出该存储结构的定义 3 详细设计 各个算法实现的源程序 对每个题目要有相应的源程序 可以是一组源程序 每个功能模块采 用不同的函数实现 源程序要按照写程序的规则来编写 要结构清晰 重点函数的重点变量 重点功能部分要加上 清晰的程序注释 4 调试分析 包括测试数据 测试输出的结果 时间复杂度分析 和每个模块设计和调试时存在问题的思考 问题是哪些 问题如何解决 算法的改进设想 5 课设总结 总结可以包括 课程设计过程的收获 遇到问题 遇到问题解决问题过程的思考 程序调试 能力的思考 对算法设计与分析这门课程的思考 在课程设计过程中对 算法设计与分析 课程的 认识等内容 4 课程设计报告打印稿 七 推荐参考资料 教 材 算法设计与分析 Anany Levitin 著 潘彦译 清华大学出版社 2007 算法设计与分析 宋 文 等编 重庆大学出版社 2001 参考书 1 算法设计与分析 周培德 电子工业出版社 2000 2 算法设计与分析 王晓东 电子工业出版社 2004 指导教师 签名日期 年 月 日 系 主 任 审核日期 年 月 日 目 录 1 引言引言 1 2 贪婪算法的概述贪婪算法的概述 1 2 1 什么是贪婪算法 1 2 2 贪婪算法的特性 1 2 3 贪婪算法解决问题的步骤 2 2 4 贪婪算法的优缺点 2 3 贪婪算法的应用贪婪算法的应用 3 3 1 贪婪算法在资源分配问题中的应用 3 3 2 贪婪算法在布线问题中的应用 4 3 3 贪婪算法在 0 1 背包问题中的应用 6 3 3 1 传统的贪婪算法解决方案 6 3 3 2 改进的贪婪算法策略 7 4 总结与展望总结与展望 9 参考文献参考文献 10 利用贪婪法实现多种实际问题 1 引言引言 为了满足人们对大数据量信息处理的渴望 为解决各种实际问题 计算机算法学得 到了飞速的发展 线性规划 动态规划 贪婪策略等一系列运筹学模型纷纷运用到计算 机算法学中 产生了解决各种现实问题的有效算法 虽然设计一个好的求解算法更像是 一门艺术 而不像是技术 但仍然存在一些行之有效的能够用于解决许多问题的算法 设计方法 可以使用这些方法来设计算法 并观察这些算法是如何工作的 一般情况 下 为了获得较好的性能 必须对算法进行细致的调整 但是在某些情况下 算法经 过调整之后性能仍无法达到要求 这时就必须寻求另外的方法来求解该问题 目前常用的算法设计技术有分治法 回溯法 贪婪法 动态规划算法 分支限界 法等 其中分治法 回溯法主要用于设计非数值问题的算法 而贪婪法 动态规划算法 分支限界法则主要用于设计数值最优化问题的算法 贪婪法是一种求最优解问题的最 直接的设计技术 它不是对所有问题都能得到整体最优解 但对许多问题可能产生整 体最优解 2 贪婪算法的概述贪婪算法的概述 2 2 1 什么是贪婪算法什么是贪婪算法 贪婪算法是一种对某些求最优解问题的更简单 更迅速的设计技术 用贪婪法设 计算法的特点是一步一步地进行 常以当前情况为基础根据某个优化测度作最优选择 而不考虑各种可能的整体情况 它省去了为找最优解要穷尽所有可能而必须耗费的大 量时间 它采用自顶向下 以迭代的方法做出相继的贪心选择 每做一次贪心选择就将 所求问题简化为一个规模更小的子问题 通过每一步贪心选择 可得到问题的一个最优 解 虽然每一步上都要保证能获得局部最优解 但由此产生的全局解有时不一定是最 优的 所以贪婪法不要回溯 贪婪算法是一种改进了的分级处理方法 其核心是根据题意选取一种量度标准 然后将这多个输入排成这种量度标准所要求的顺序 按这种顺序一次输入一个量 如 果这个输入和当前已构成在这种量度意义下的部分最佳解加在一起不能产生一个可行 解 则不把此输入加到这部分解中 这种能够得到某种量度意义下最优解的分级处理 方法称为贪婪算法 对于一个给定的问题 往往可能有好几种量度标准 初看起来 这些量度标准似 乎都是可取的 但实际上 用其中的大多数量度标准作贪婪处理所得到该量度意义下 的最优解并不是问题的最优解 而是次优解 因此 选择能产生问题最优解的最优量 度标准是使用贪婪算法的核心 一般情况下 要选出最优量度标准并不是一件容易的事 但对某问题能选择出最 优量度标准后 用贪婪算法求解则特别有效 最优解可以通过一系列局部最优的选择 即贪婪选择来达到 根据当前状态做出在当前看来是最好的选择 即局部最优解选择 然后再去解做出这个选择后产生的相应的子问题 每做一次贪婪选择就将所求问题简 化为一个规模更小的子问题 最终可得到问题的一个整体最优解 2 2 贪婪算法的特性贪婪算法的特性 利用贪婪法解决实际问题 2 贪婪算法及贪婪算法可解决的问题通常大部分都有如下的特性 1 有一个以最优方式来解决的问题 为了构造问题的解决方案 有一个候选的 对象的集合 比如不同面值的硬币 2 随着算法的进行 将积累起其它两个集合 一个包含已经被考虑过并被选出 的候选对象 另一个包含已经被考虑过但被丢弃的候选对象 3 有一个函数来检查一个候选对象的集合是否提供了问题的解答 该函数不 考虑此时的解决方法是否最优 4 还有一个函数检查是否一个候选对象的集合是可行的 也即是否可能往该集 合上添加更多的候选对象以获得一个解 和上一个函数一样 此时不考虑解决方法 的最优性 5 选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解 6 最后 目标函数给出解的值 为了解决问题 需要寻找一个构成解的候选对象集合 它可以优化目标函数 贪婪算 法一步一步的进行 起初 算法选出的候选对象的集合为空 接下来的每一步中 根据 选择函数 算法从剩余候选对象中选出最有希望构成解的对象 如果集合中加上该对象 后不可行 那么该对象就被丢弃并不再考虑 否则就加到集合里 每一次都扩充集合 并检查该集合是否构成解 如果贪婪算法正确工作 那么找到的第一个解通常是最优 的 2 3 贪婪算法解决问题的步骤贪婪算法解决问题的步骤 贪婪算法的一般解题步骤 设计中一类非常重要的问题 每一个最优化问题都包含一组约束条件和一个优化函 数 满足约束条件的问题求解方案称为问题的可行解 使优化函数取得最优值的可行 解称为问题的最优解 贪婪算法是解决最优化问题的一种基本方法 它采用逐步构造 最优解的思想 在问题求解的每一个阶段 都做出一个在一定标准下看上去最优的决 策 决策一旦作出 就不可再更改 制定决策的依据称为贪婪准则 使用贪婪算法解 决问题 通常需要做好以下几个方面的工作 1 明确问题的求解目标 2 分析问题所包含的约束条件 3 建立优化函数 优化函数通常可以通过综合分析问题的求解目标及约束条件归 纳出来 4 制定贪婪准则 清楚问题的求解目标 所包含的约束条件及优化函数之后 就 可以着手制定一个可行的贪婪准则 贪婪准则的制定是用贪婪算法解决最优化问题的 关键 它关系到问题能否得到成功解决及解决质量的高低 2 4 贪婪算法的优缺点贪婪算法的优缺点 贪婪算法是一种重要的算法设计策略 而且其效率高 贪婪算法并不从整体最优考 虑 它所做出的选择只是在某种意义上的局部最优选择 即在当前看来最好的选择 希望 通过每次所做的贪婪选择导致最终结果是问题的一个最优解 贪婪算法具有良好的爬 坡能力 一般情况下该算法都可以较快地求出满足计算精度要求的近似最优解 当算 利用贪婪法实现多种实际问题 3 法不能在限定的计算时间内找到满足问题要求的近似最优解时 给出一个可行解及计 算误差 作为决策参考 但是随着问题规模和复杂度的不断提升 单一的算法在其收 敛性和求解速度等方面已经表现出局限性 即使贪婪算法的效率很高 它也只适用于 少量的实例 假设某职工的工资为 638 元 要求统计并输出应发给该职工面值 100 元 50 元 20 元 10 元 5 元 2 元 1 元的人民币各多少张 使总张数最少 我们该发给他多少 张人民币呢 答案可以是 638 张面值 1 元的人民币 可以是 638 2 319 张面值 2 元的 人民币 无论发给该职工人民币多少张 他拿到的人民币总和都应等于他自己的 工资数 要发给该职工 638 元的工资 并使总张数最少 直觉告诉我们 应先给他 6 张面值 100 元的人民币 第 7 张不能再给 100 元的 也不能给 50 元的 否则该职工实 际拿到的工资将会超过他应得的工资 显然 第 7 张应为面值 20 元的人民币 同理 第 8 张为面值 10 元的人民币 第 9 张为面值 5 元的人民币 第 10 张为面值 2 元的人 民币 第 11 张为面值 1 元的人民币 该职工共拿到人民币 11 张 分别为面值 100 元 的 6 张 面值 50 元的没有 面值 20 元 10 元 5 元 2 元和 1 元的各 1 张 这样 不 但满足了约束条件即 100 6 20 10 5 2 1 1 638 而且使该职工拿到的人民币张 数最少 把以上操作方法归纳出来就是一种可行的贪婪准则 按面值从大到小的顺序 分发人民币 并始终保证职工实际拿到的工资不超过他应得的工资 当贪婪算法面对不同的货币系统 或者缺少某种面值的货币 或者某种面值的货币 数目有限等情况时 它可能只能找出一个次优解或是根本找不到解 假如给出的面值 中没有 2 元和 1 元或是限定面值的张数时 贪婪算法就不能解决了 因此要具体问题 具体对待 可以将贪婪算法与其他算法结合起来应用 多种算法相结合使用的混合优 化策略已经逐渐成为新的研究热点 3 贪婪算法的应用贪婪算法的应用 贪婪算法的基本思路 从问题的某一个初始解出发逐步逼近给定的目标 以尽可能 快地求得更好的解 当达到某算法中的某一步不能再继续前进时 算法停止 该算法存在的问题 1 不能保证求得的最后解是最佳的 2 不能用来求最大或最 小解问题 3 只能求满足某些约束条件的可行解的范围 3 1 贪婪算法在资源分配问题中的应用贪婪算法在资源分配问题中的应用 下面介绍争用 2 个甚至多个资源时的安排 现有 m 个资源 如 m 个多媒体教室 有 n 个课程的集合 E 1 2 n 其中每 个课程都要求使用一个资源 而在同一时间内只允许一个课程使用一个资源 每个课 程使用某一资源时 为提高利用率 按照资源大小的非递减顺序安排 如果资源大小一 样 可省去这个排序工作 每个课程 i 都有一个要求使用资源的起始时间 si 和一个 结束时间 fi 且 si fj 或 sj fi 时 课程 i 与课程 j 相容 设 A 是所要求安排的课程的 m 个最大相容课程子集 即用 A i j 存储对最小教室 利用贪婪法解决实际问题 4 所选择的课程 A i m 存储对最大教室所选择的课程 若课程 i 在集合 A i x 中 x 1 2 m 则 A i x 必为 true 存入其课程序号 变量 J x 用以记录最近一 次加入到 A i x 中的课程 已知的各课程的起始时间和结束时存储于数组 s 和 f 中 且按结束时间的非减序 f1 f2 f J 1 then Begin A i 1 I J 1 i End Else For k 0 to m 1 do If s i f J k then Begin A i k I J k i End End 按照上述贪婪策略 将 m 个资源按照利用率非递减排序 在年 n 个课程按结束时间 非递减排序后 运用贪婪算法依次把相容课程加入到 m 个相容课程集合中 使该问题 在相容课程安排最多时利用率也最大 在 n 个课程和 m 个资源事先排队的情况下 用 贪婪策略解此问题可以获得最佳解 其计算复杂度至多是 O m n 在众多的算法中执 行时间最短 3 2 贪婪算法在布线问题中的应用贪婪算法在布线问题中的应用 假定要将一组电子元件安装在线路板上 给定一个连线矩阵 CON 和一个位置距离 矩阵 DIST 其中 CON i j 等于元件 i 和元件 j 间的连线数目 DIST r s 是此线路板中位 置 r 和位置 s 间的距离 将这 n 个元件各自放在线路板的某位置上就构成一种方案 布线 成本是 CON i j DIST r s 乘积之和 其中元件 i 放在位置 r 元件 j 放在位置 s 设计一 种布线方案 找出其布线成本是最小值 电路板布线问题分析 电路板上 n 个位置分别标记为 p1 p2 p3 pn 这 n 个位置构成一个无向图 n 个顶点 n n 1 2 条边 任意两个位置之间的距离由矩阵 DIST 给出 记这个图为 G V E 同样 对 n 个元件也标上记号 为 e1 e2 e3 en 这 n 个元件的一个全排列就对应于一种布线方 利用贪婪法实现多种实际问题 5 案 显然 每一个排列也构成一个无向图 n 个顶点对应于 n 个元件 而任意两个顶点之间是 否有线连接由 CON 给出 即 CON r s 0 则表示顶点 元件 er es 之间有边相连 否则 CON r s 0 时 顶点 元件 er es 之间无边相连 这样 也构成一个无向图 G V E 不 考虑顶点 边所代表的具体含义 显然 V V E E 而且对于每一条边 e E 都有 e V 所以 可以将 V 看成是 G 的一个顶点覆盖 所以 电路板布线问题可以看成一个 带权值的顶点覆盖问题 针对本文中的电路板布线问题 考虑 贪婪算法 回溯法 作为求解问题的近似算 法 考虑电路板布线问题的代价函数定义 直观的感觉应该是将连线多的元件尽量放 在距离短的两个位置上 按照这样的方法 每放一次元件 能够使得布线代价增加得 小一些 所以 贪婪策略定义为 按照连线数与位置距离比值递减的次序安装元件 按照这种策略 可以得到一种布线方式 同时 考虑到每一个元件位置对 将两个元 件安装在两个位置上有两种不同情况 这样采用回溯法遍历每一对元件位置对的不同 安装方式 从中找出相对最优的布线方式 采用这种近似算法最大的优点是效率高 速度快 在短时间内找到一定精度的解 算法描述 1 输入连线矩阵 CON 和位置距离矩阵 DIST 2 贪婪算法 找出一种布线方式 3 回溯法 对 2 中找到的布线方式 所有的可能交换的 元件位置对进行回溯搜索 得到一种相对较优布线方式及其布线总代价 4 输出结果 本文中采用的贪婪策略为 按照连线数与位置距离比值递减的次序安装元件 在使用 这种贪婪策略情况下 需要考虑以下几个问题 1 在当前连线矩阵 tmpCON 中选中最大连线数 确定的关联的两个元件 e1 e2 不能 都出现在链表 dis con 中 出现这种情况应该舍弃 并修改 tmpDIST 使得不会再次出现 e1 e2 被同时选中的情况 2 当确定的两个相关联的元件 e1 e2 中 假设有一个元件 e2 已经出现在链表 dis con 中 应该从 e2 对应的位置 p2 在当前位置矩阵 tmpDIST 进行搜索 而且确定的另一个 位置 P1 没有出现在 dis con 3 当确定的两个相关联的元件 e1 e2 都没有出现在 dis con 中 应该使在当前位置矩 阵 tmpDIST 确定的两个位置 p1 p2 都没有出现在 dis con 中 4 当在当前 tmpDIST 中确定位置 P1 P2 失败时 应该丢弃当前选定的元件 e1 e2 并 且修改在 tmpCON e1 e2 对应的值 鉴于以上的情况 设计的基于 贪婪算法 的算法如下 1 定义两个矩阵 tmpDIST 和 tmpCON 并用 CON 和 DIST 初始化这两个矩阵 2 在矩阵 tmpCON 选择最大连线数 确定关联的两个元件 e1 e2 3 判断两个元件 e1 e2 是否已经在 dis con 中 返回元件 e1 e2 在 dis con 中的个数 num 如果 num 2 即 e1 e2 两个元件均在 dis con 元件位中 修改矩阵 tmpCON 中元件 e1 e2 对应的位置 赋值为 1 使之不能再次被选中 转向 2 否则 转向 4 4 如果 num 0 即选出的 e1 e2 两个元件均不在 dis con 元件位中 在矩阵 tmpDIST 利用贪婪法解决实际问题 6 中选出两个位置 p1 p2 使 p1 p2 不在 dis con 位置位中 如果 num 1 即选出的 e1 e2 两个 元件有一个已经在 dis con 元件位中 假设为 e2 从 e2 对应的位置 P2 进行搜索 选出另一 个位置 p1 并且保证 p1 没有出现在 dis con 中 如果能够选出 p1 p2 转向 5 否则 修改矩 阵 tmpCON 中元件 e1 e2 对应的位置 赋值为 1 并转向 2 5 将 e1 e2 p1 p2 分别对应选入 dis con 的元件位和位置位中 若 num 0 标记这一个 元件位置对在 dis con 中对应的标志位为 0 若 num 1 标记这一个元件位置对在 dis con 中对应的标志位为 01 或 10 1 表示对应的元件和位置不是第一次选入 dis con 中 修 改矩阵 tmpCON 中元件 e1 e2 对应的元素 赋值为 1 修改矩阵 tmpDIST 中 p1 p2 对应的 元素 赋值为 6 判断元件是否已经全部选出 若全部选出 则保存结果 一种布线方式结束贪婪 算法 否则转向 2 在本文中 采用一个一维数组 Ex m 来模拟对一个深度为 m 的二叉树进行回溯搜索 定义运算 当 Ex i 1 2 时 令 Ex i 0 Ex i 1 Ex i 1 1 这样 对 Ex i 加 1 就完成了从 二叉树的第 i 层向第 i 1 层的回溯 对 Ex i 进行加 1 操作 直至 Ex i 1 i 1 2 n 以此 来模拟二叉树的回溯 回溯法 的具体算法 1 统计 dis con 中元件位置对对应的标志位为 00 的个数 m 在贪婪算法所得到的 布线方案中有 m 对元件位置对可以互换 算法需对一个深度为 m 的二叉树的叶节点进 行搜索 共需要搜索 2m 次 初始化布线代价和最小值 min 及其对应的布线方案 x 1 n 2 对于一个叶节点计算其布线代价和 sum 若 sum min 更新布线代价和最小值 min 及 其对应的布线方案 x 1 n 3 判断是否搜索完毕 若搜索完毕 转向 4 否则转向 2 4 输出布线代价和最小值 min 及其对应的布线方案 x 1 n 根据上面的推导 总的算法复杂度可以表示为 n T1 2p1n T2 可以看出 该算 法复杂度与贪婪算法循环次数 n 一次选择得到有效元件位置对的概率 P1 有关 对于 n 和 P1 很难有一个精确的估计 所以采用了程序仿真 以得到估计值 对于电路板布线问题的复杂度 我们给出一般性的结论 当 N 0 wi 0 vi 0 1 i n 要求找出一个 n 元 0 1 向量 x1 x2 xn xi 0 1 1 i n 使得 Wixi c 而且 vixi 达到最大 用贪婪算法来设计求解 0 1 背包问题 首先要选出 最优的量度标准 可选择的贪婪策略有三种 每个贪婪策略都采用多步过程来完成背包 的装入 在每一步过程中利用贪婪策略选择一个物品装入背包 一种贪婪策略是将目标函数作为量度标准 即每装入一件物品 使背包获得最大可能 的价值 其具体步骤是 从剩余的物品中 选出可以装入背包的价值最大的物品 利用这 种规则 价值最大的物品首先被装入 假设有足够容量 然后是下一个价值最大的物品 如 此继续下去 考虑 n 3 w 20 5 4 v 25 15 15 c 20 当利用价值贪婪策略 时 获得的解为 x 1 0 0 这种方案的总价值为 25 而最优解为 0 1 1 其总价 值为 30 可见 这种策略不能保证得到最优解 其原因在于 虽然每一步获得了效益值 最大的增加 但背包可用容量消耗过快 由此可知 按物品价值的非增次序装包不能得到 最优解 由此 用重量作为量度 采用重量贪婪策略 让背包重量尽可能慢地被消耗 这就 要求按物品重量的非降次序来把物品放入背包 即从剩下的物品中选择可装入背包的重 量最小的物品 虽然这种规则对于前面的例子能产生最优解 但在一般情况下则不一定 能得到最优解 考虑 n 2 w 10 20 v 5 100 c 25 当利用重量贪婪策略时 获得的解为 x 1 0 比最优解 0 1 要差 这是因为重量虽然慢慢地被消耗 但价值 没能迅速地增加 为此 采用在价值的增长速率和重量的消耗速率之间取得平衡的量度 标准 单位价值贪婪策略 这种选择策略为 从剩余物品中选择可装入包的 vi wi 值最大的物品 这种策略也不能保证得到最优解 利用此策略解 n 3 w 20 15 15 v 40 25 25 c 30 时 获得的解为 x 1 0 0 而最优解为 x 0 1 1 通过上述分析看到 运用这三种策略 都不一定能得到 0 1 背包问题的最优解 这是因 为它无法保证最终能将背包装满 部分背包空间的闲置使每个单位空间所具有的价值降 低了 然而 在随机产生的背包问题中 第三种策略获得最优解的几率明显大于前两种 传统贪心算法解决0 1 背包问题的具体算法 void CCompute Greedy01KnapsackQ value 为所取物品的总价值 weight 为所取物品的总重量 if getRestrictNo 1 return 若约束个数大于 1 则不能使用贪婪法 long N getSize 获取背包个数 float value 0 weight 0 for int i start i m fRestrict 0 N continue value m fDestination i 目标函数 weight m fRestrict 0 i 约束函数 利用贪婪法解决实际问题 8 setResult value 该算法的主要计算时间在于将各种物品依其单位重量的价值从大到小排序 因此 算法的计算时间上界为O nlogn 3 3 2 改进的贪婪算法策略 k 阶优化方法 k optimal 0 1 背包问题是一个 NP 复杂问题 对于这类问题 也许根本就不可能找到具有多 项式时间的算法 虽然按 vi wi 非递增的次序装入物品不能保证得到最优解 但它是一 个直觉上近似的解 希望它是一个好的启发式算法 且大多数时候能很好地接近最后算 法 是否存在一个 x x 100 使得采用单位价值贪婪策略求解最优解的结果与最优值 相差在 x 以内 经过验证 这种情况是不可能的 例如 对于 n 2 w 1 y v 10 9y c y 贪心算法结果为 x 1 0 最终的价值为 10 而当 y 10 9 时 最优解 的值为 9y 因此 贪婪算法的计算结果与最优解的差与最优解之间的比例为 9y 10 9y 3 100 当 y 值较大时 这个值趋近于 100 但是 我们可以利用贪心算法来提供 解 使解的结果与最优解的值之差在最优值的 x x 100 之内 首先将最多 k 件物品 放入背包 如果这 k 件物品重量大于 c 则放弃它 否则 剩余的重量用来考虑将剩余物 品按 vi wi 递减的顺序装入 通过考虑由启发法产生的解法中最多为 k 件物品的所有 可能的子集来得到最优解 考虑 n 4 w 1 2 5 6 p 3 5 10 11 c 7 当 k 0 时 背包按物品单位价 值非递增顺序装入 首先将物品 1 放入背包 然后是物品 2 背包剩下的容量为 4 个单 元 剩下的物品没有一个合适的 因此解为 x 1 1 0 0 此解获得的价值为 8 现在考虑 k 1 时的贪婪启发法 最初的子集为 1 2 3 4 子集 1 2 产生与 k 0 时相同的结果 考虑子集 3 置 x3 为 1 此时还剩 2 个单位的容量 按单位价值非递增顺序来考虑如何利用这 5 个单位的容量 首先考虑物品 1 它适合 因 此取 x1 为 1 这时仅剩下 1 个单位容量了 且剩余物品没有能够加入背包中的物品 通 过子集 3 开始求解得结果为 x 1 0 1 0 获得的价值为 13 若从子集 4 开始 产 生的解为 x 1 0 0 1 获得的价值为 14 考虑子集大小为 0 和 1 时获得的最优解 为 1 0 0 1 这个解是通过 k 1 的贪心启发式算法得到 若 k 2 除了考虑 k 0 时 总的时间开销为 O nk 1 而实际测试的性 能要更好些 改进的贪婪算法解决 0 1 背包问题的具体算法描述 void CCompute ImprovedGreedy01Knapsack if getRestrictNo 1 return 若约束个数大于 1 则不能使用贪婪法 利用贪婪法实现多种实际问题 9 long N getSize 获取背包个数 for int start 0 start N start float value 0 weight 0 For int i start i m Restrict 0 N continue value m fDestination i 目标函数 weight m fRestrict 0 i 约束函数 if value getResultQ 获取当前已有的最大价值 setResult value 设置当前最大价值 setResult value 0 1 背包问题是一个NP 复杂问题 尽管已进行了多年的研究 目前还没有一个 NP 完全问题有多项式时间算法 利用优化的贪心算法求解0 1 背包问题 虽然不能保 证一定得到最优解 但是我们能够在O nk 1 的时间复杂度内 获得0 1背包问题最 优解的很好近似 这也是解决NP 类问题的一个可接受的很好的解决方案 4