背包问题的若干解法探讨.doc

哈哈 尔尔 滨滨 师师 范范 大大 学学 学士学位论文开题报告学士学位论文开题报告 论文题目 0 1 背包问题的若干解法探讨 学生姓名 指导教师 年 级 2004 级 专 业 计算机科学与技术 2008 年 3 月 课题研究的主要内容和方法 研究过程中的主要问题和解决办法 主要内容 0 1 背包问题求解的多种方法 方 法 1 0 1 背包问题的动态规划算法 2 求解背包问题的一种新的近似算法 3 一种求解 0 1 背包问题的快速蚁群算法 4 0 1 背包问题的非线性降维近似算法 主要问题 程序代码的主要编写及实现 解决方法 通过实际操作和向指导教师求教 课题研究起止时间和进度安排 起止时间 2008 年 1 月 2008 年 5 月 进度安排 指导教师可根据实际情况适当安排 2008 1 15 2008 3 1 确定论文题目 查找资料 撰写开题报告 2008 3 2 2008 3 20 查找资料 进一步分析题目研究内容 2008 3 21 2008 4 10 撰写论文并送老师第一次审查 2008 4 11 2008 4 30 论文第二次修改 老师第二次审查 2008 5 1 2008 5 10 论文第三次审查 修改并作毕业答辩前准备 交论文 答辩 I 摘要摘要 一个在运筹学领域里常见的典型 0 1 背包难题 工厂里的下料问题 管理中 的资源分配 资金预算 投资决策 装载问题等均可建模为背包问题 该问题的求解 方法的研究无论是在理论上 还是在实践中都具有重要意义 对于背包问题 己有的求 解方法可分为精确算法 如动态规划 分支定界等 和近似算法 如贪婪法 蚂蚁算法 遗传算法等 两大类 因为精确算法的时间复杂性都是呈指数增长的 所以从六十年代 逐渐提出了一些近似算法 在阅读了大量中外文献的基础上 使我充分了解了一种基于 0 1 背包问题的动态 规划算法和蚂蚁算法 文章在开篇综述背包问题的一些基本情况后 接着介绍了 0 1 背包问题的一些基本观点 方法和理论 包括数学模型 算法描述 算法分析 动态 规划 群蚁算法 非线性将维算法等三种算法的比较与设计 以及 0 1 背包问题的程 序的源代码 在根据背包的问题的具体情况的改进之后 我们了解了背包问题基于精 确算法和一个近似转化优化算法并且根据此算法用 C 语言设计了背包问题 0 1 背包 的设计充分结合了 C 语言的特点 具有高性能和高的可扩展性 提供了可扩展的接口 以方便其他应用程序扩展和调用 作为 0 1 背包开发的一部分 我结合背包问题的三种方法 在本篇中进行了具体 介绍 本文在每种算法的最后面给出了算法的代码程序 从运行结果来看 动态规划 算法的运行效率非常高 求解 0 1 背包问题的精确算法不能在较短时间内求解大规模 0 1 背包问题 使其实用性受到限制 针对该问题 给出求解 0 1 背包问题的非线性降 维算法 并进行了数值实验 验证了算法的有效性 该算法属于近似算法 相对其他 一些近似算法 计算结果更为精确 关键字关键字 0 1 包问题 动态规划 群蚁算法 非线性降维算法 II 目目 录录 第一章第一章 引言引言 1 1 历史背景 1 1 2 背包问题各种形式的数学模型 2 1 3 0 1 背包问题 3 1 3 1 问题的提出 3 1 3 2 整数规划问题 4 1 4 本文的结构和主要创新点 5 第二章第二章 0 1 背包问题的算法描述与设计背包问题的算法描述与设计 2 1 背包问题的数学描述 6 2 2 0 1 背包问题动态规划算法的探讨 6 2 2 1 动态规划算法原理 7 2 2 2 0 1 背包问题最优性原理 9 2 2 3 典型例题 10 2 2 4 动态规划向前处理法的递推过程 12 2 2 5 图解法求解背包 13 2 2 6 多条件限制的 0 1 背包问题 14 2 2 7 动态规划的程序代码 16 2 2 8 总结 21 2 3 基于蚁群算法求解 0 1 背包问题 21 2 3 1 蚁群算法的基本原理 21 2 3 2 蚁群系统模型 22 2 3 3 初始化 23 2 3 6 基本蚁群算法 25 2 3 7 一种求解 0 1 背包问题的快速蚁群算法 25 2 3 8 总结 27 2 4 0 1 背包问题的非线性降维近似算法 28 2 4 1 0 1 背包问题 KNAPSACK PROBLEM 简称 KP 可定义为 28 2 4 2 理论基础和算法 28 2 4 3 总结 30 2 5 其他算法的简介 30 2 5 1 用回溯法解 0 1 背包问题 31 2 5 2 分枝限界 BRANCH AND BOUND 31 第三章第三章 0 1 背包问题多种算法的分析与比较背包问题多种算法的分析与比较 3 1 动态规划的分析与比较 33 3 2 群蚁算法的分析与比较 33 3 2 1 实验结果及结论 33 3 3 近似算法的分析与比较 34 3 3 1 试验结果及结论 34 结结 论论 参考文献参考文献 37 Abstract 38 1 第一章 引言 本章将首先从背包问题的历史背景谈起 讲述什么是背包问题各类背包问题的数 学模型与应用 随后讨论 0 1 背包问题的代表性和重要理论价值 最后叙述文章的结 构和本文的主要工作和创新点 1 11 1 历史背景历史背景 背包问题 Knapsack problem 在 50 年代末期被 Daunts 首次提出之后 在近年来被 广泛的研究 这不仅是因为背包问题在工业和金融投资领域能得到直接的应用 更是 因为很多理论上的原因 很多整数规划的问题的解决都依赖于一个高效的背包问题解 法 在这些整数规划问题中 每当需要定界的时候我们都需要解决一个背包子问题 因 此 一个高效的背包问题解法就显得非常有必要 所有的背包问题都可以定性的描述为 从给定的物品集合中选择出一个子集 在 不超出所有背包的负载的前提下 实现利益最大化 背包问题的不同种类的判定 是 根据物品和背包的类型 在 0 1 背包问题 0 1 Knapsack Problem 中 每一个物品最多被 选择一次 而与之相对应的有界背包问题 Bounded Knapsack Problem 中能选择的物品 数则可以在某个范围内取值 再比如多选择背包问题 Multiple choice Knapsack Problem 是 说某几个物体必须选择一个或多个 而多背包的问题 Mulct 加 le Knapsack Problem 则 是说某些背包必须同时被装满 在这些背包问题家族中 最通用的形式是多条件约束 背包问题 Multi constrained Knapsack Problem 而这在实质上就是正系数的整数规划问 题 Integer Programming 背包问题属于组合最优化问题 一般的最优化问题 Optimization Problem 由目标函 数 Objective Function 和约束条件 Constraints 两部分构成 1 2 1 1 1 2 将满足所有约束条件的解空间 S 称为可行域 Feasible Region 可行域中的解称为 可行解 Feasible Solution 将可行域中使目标函数最小的解称为最优解 Optimal Solution 对于最大化问题 可将目标函数乘以 1 转化为最小化问题求解 当 X 或 S 为离散集合构成的解空间时 这类最优化问题称为组合最优化问题 Combinatorial Optimization Problem 基于精确的 0 1 背包问题算法研究 衡量一个算法的好坏通常用算法中的加 减 乘 除和比较等基本运算的总次数 通过实例在计算机中计算时的二进制输入数据的大小关系来度量 我们对实例的二进 制输人长度和算法的基本计算总次数是粗略估计的 一般是给予一个上限 一个求解 实例 I 的算法的基本计算总次数 C 同实例 I 的计算机二进制输入长度 d I 的关系常用符 号 C I f d 1 O g d I 表示 它的含义是 求解实例 I 的算法的基本计算总次数 C I 是实例输入长度 d I 的一个函数 这个函数被另一个函数 g x 控制 即存在一个函 数 g x 和一个正常 a 使得 1 2 其中 g x 的函数特性决定了基本计算总次数的性能 假设问题和解决该问题的一个算法己经给定 如给定该问题的一个实例 I 存在多 项式函数 g x 使得成立 我们称该算法对实例 I 是多项式时间算法 若存在 g x 为多项 2 式函数且对该问题任意的一个实例 I 都有 1 2 成立 则称该算法为解决该问题的多项 式时间算法 对于给定的一个优化问题 若存在一个求解该问题最优解的算法 一个 多项式的实函数 g x 和常数 a 使得对给定优化问题的任何一个实例成立 则称给定 的优化问题是多项式时间可解问题 或简称多项式问题 1 所有多顶式问题集合记为 P Polynomial 并不是所有的组合最优化问题都找到了求解最优解的多项式时间算法 也就是说 还不能肯定一些组合最优化问题是否属于 P 经过几代数学家的努力 他 们研究整理了一类难以求解的组合最优化问题 迄今为止 这些问题还没有一个有能 求得最优解的多项式时间算法 这一类组合最优化问题归为所谓的 NP Hard 受人类 认识能力的限制 目前人们只能假设这一类难解的组合最优化问题不存在求解最优解 的多项式时间算法 所有的背包问题都属于 NP Hard 问题 这就是说我们设计出背包 问题的多项式时间算法的可能性非常小 也即是说对于背包问题而言 我们除了枚举 整个解空间而外就无法求得背包问题的精确解 2 然而 下面的一些技术的应用 使得 我们的枚举可能变得相对容易一些 这些技术也是目前大多数算法设计思想的一个小 结 分枝定界 Branch and boon 3 几乎是一个完整的枚举 只是使用上下界 分支定 界枝 的方法避免扩展了一些不可能导出最优解的结点 动态规划 Dynamic Programming 4 动态规划的方法是在宽度优先搜索的基础上 添加了一些优先规则 有的时候也可以加入边界测试 因此 动态规划方法在某些时 候可以看作分枝定界的改进版本 状态空间松弛 State Space Relaxation 5 在可能牺牲优化质量的前提下 减少状态 空间的大小 从而极大地减少算法的时间复杂度和空间复杂度 目前背包问题的很多 高效近似解法都来源于此种思想 预处理 Preprocessing 6 通过一些特别的测试能预先确定出在最终的解向量中某 些决策变量的取值 从而事先把他们排除在外 减小问题的规模 1 21 2 背包问题各种形式的数学模型背包问题各种形式的数学模型 通过阅读大量文献 我了解到 0 1 背包问题的五种类型的背包问题的数学定义 这些类型基本上涵盖了大多数的常规应用 在这些类型的背包问题中 我们用 Pi 表示 选择物品 J 获得的效益 用 Wj 表示物品 J 的重量 物品需要放在承重能力为 C 的包 裹中 同时我们还约定 所有这些系数 Pj 与 Wi 的和都是正整数 1 0 1 背包题 7 0 1 Knapsack Problem 0 1 背包问题是从有 n 个物品的物品集选取一个子集 在总体积不超过包裹容量 c 的前提下 使得相对应的利益实现最大化 可以用以下的公式进行形式化的描述 1 和 1 或 0 1 1 1 3 其中如果选择物品 J 那么决策变量 Xj取 1 否则取 0 2 有界背包问题 8 Bounded Knapsack Problem 物品 J 最多可以选择 mj 个 那么有界背包问题可以描述为 1 和 1 或 0 1 1 3 1 4 3 无界背包问题 9 Unbounded Knapsack Problem 无界背包问题实际上是有界背包问题的扩展 每个物品可以任意的取 1 和 1 或 0整数 1 1 5 但是因为背包的承重能力有限 每个物品的数目不可能取到无穷大 因此上它仍 旧是一个有界背包问题 4 多选择背包问题 10 Multi choice Knapsack Problem 多选择背包问题是 0 1 背包问题的另外一种扩展 扩展不是针对数目进行的 而 是针对物品的类型 即是说 从 k 类物品 Ni i 1 k 中选择出物品 j 使得最终的总获 益最大 数学定义如下 1 1 1 1 0 1 1 1 6 这里如果物品 j 被从第 i 类中选择出来 那么决策变量 Xij 1 的限定条件 保证了 每类物品能且只能选择一个 5 最大子集和问题 11 Subset sum Problem 如果 0 1 背包问题中每个物品的 Pj都和它的 wj相等 就构成了最大子集和问题 数学定义如下 1 和 1 或 0 1 1 1 7 以上的这些类型的背包问题无论在理论上 还是在实践中都具有非常多的应用 在理 论上 背包问题是很多组合优化问题的子问题 背包问题研究上的任何一个进步都会 使得这些问题的解决受益 在实践环节上 背包问题并不局限于装箱问题 在投资问 题中 某投资者用 c 个货币单位去做投资 有 n 个项目可供选择 其中第 j 个工程的投 入 wj而能获得 pi的利润 这样的投资问题就是一个 0 1 背包问题 除了以上描述的简单的应用之外 背包问题还更主要的应用于货物装载 股票投 资 预算控制 财务管理等问题 Differ 和 Hemll naslll 根据最大子集和问题设计了 背包公开加密算法 Maretlol 和 Tohtl 证明了计算机中双处理器任务分配问题也是一个 最大子集和问题 1 31 3 0 10 1 背包问题背包问题 在 1 1 中 我们曾经谈过 背包问题可以看成普通整数规划问题的特殊形式 非常 有意思的是 相反的情况也是成立的 也就是说 任何一个多条件的整数规划问题都 可以等价的转化为一个单条件的整数规划问题 继而转化为 0 1 背包问题 1 3 11 3 1 问题的提出问题的提出 0 1 背包问题 knapsack problem 是计算机学科中的一个经典算法问题 也是被证明 4 了的 NP 难解问题 围绕着这个问题求解法很多 本文针对 0 1 背包问题 采用动态 规划算法 群蚁算法 非线性降维算法三种不同方法进行求解和算法分析 并通过各 种算法的实现 研究了 0 1 背包问题的实质 给定 n 种物品和 1 个背包 物品 i 的重量是 wi 其价值为 vi 包的容量为 c 问应 如何选择装入背包中的物品 使得装入背包物品的总价值最大 在选择装入背包的物品时 对每种物品 i 只有两种选择 即装入背包 不装入背包 不能将物品 i 装入背包多次 也不能只装入部分的物品 i 因此 该问题称为 0 1 背包 问题 此问题的形式化描述是 给定 C 0 wi 0 vi 0 1 i n 要求找一个 n 元 0 1 向量 1 2 0 或1 1 使得 1 而且 1 达到最大 1 8 数学模式 1 约束条件 1 0或1 1 1 9 1 3 21 3 2 整数规划问题整数规划问题 1 1 1 2 2 0 Xj UjXj 为整数 j 1 n 1 10 算法 1 1 令 1 1 1 2 1 2 1 11 因此 我们可以用下式给出加 g x 的上下界 1 12 其中 我们定义 取正数 满足 1 1 1 13 1 1 1 1 1 1 因此 有我们将 1 9 中的第 g x 两个约束乘上完并且加到第一个约束上 就求得到下面的问题 0 Xj UjXj 为整数 j 1 n 1 14 定理 1 1 12 5 如果选择满足 1 12 式子的条件 那么 1 9 和 1 13 就有相同的解得集合 证明 很明显 对于任意的因子 1 9 的解都将是 1 13 的解 因此我们只用证明相 反的情况 假设 x 是 1 13 的一个解 且令 1 15 很明显 K 是一个整数 因为所有的系数都是整数 我们希望证明 根据 1 12 选择得出的元可以使得 K 0 注意 1 13 中的约束条件也可以写成 G x h x 0 1 16 通过代入 1 16 我们可以得出 g x k 0 而根据 1 12 有 g x 0 kg 要在携带各种物品的总重量不超过 b 千克的限制下 使旅途中所携带物品的 总 价值 或 总效益 最大 经济活动中有许多整数规划问题与此问题等价 其数 学模型描述为背包问题在数学中实际上是一个 0 1 背包动态规划问题 假设有 n 个物 品 其质量及价值分别为 Wi 和 Ci wi 0 ci 0 i 1 2 n 背包的容量假设为 v v 0 问题选择哪些物品装入背包 可使得在背包容量的限制内所装物品的总价值最大 该 问题的数学模型为 2 1 格式中 Xi 为 0 1 背包的决策变量 Xi 1 表示将物品 i 装入背包中 Xi 0 则表示不将其 装入 目前求解问题的算法很多 我将用 0 1 的动态规划算法 群蚁算法 近似算法 来进行描述与分析 背包问题在计算理论中属于 NP 完全问题 目前对背包问题的解法 分为精确算法 如动态规划 回溯法 分支定界法等指数级方法 和近似算法 如贪心法 Lagrange 法等 两大类 霍红卫 13 曾基于罚函数修正方法 提出解决该问题的遗传算法 获得了与理论分析一致的实验结果 马良等人给出了一种新的优化方法 14 用蚁群算 法求解背包问题 但是他们仅仅是实现了蚁群算法在背包问题中的简单应用 问题的 约束条件往往不能得到满足 同时解的质量也不能得到充分保证 这里给出一种求解 背包问题的基于解的相异度的蚁群优化算法 Ant Colony Knapsack Algorithm based on Dissimilar i ty ACKAD 在算法中充分考虑收敛速度和解的稳定性 多样性 成功避 免了早熟 停滞现象 2 22 2 0 10 1 背包问题动态规划算法的探讨背包问题动态规划算法的探讨 本节结合相关教材所讲的知识 具体阐述用动态规划的向前处理法求解背包问题 的递推过程 给出了向前处理背包问题的具体实例 并用坐标图表示递推求解过程 把深奥的背包问题非常直观地表达出来 更易于理解和接受 背包是运筹学中的著名问题 指背包的容量有限 将不同体积物体放入包中 放 哪些物体才能使背包空间充分利用 这个问题具体描述为 有 N 种物品和一个可容纳 M 重量的背包 每种物品的重量为 Wi 假定将物品 i 的一部分 Xi 装入背包 就会得 到 pixi 0 xi 1 pi 0 的收益 采用怎样的装包方法才会使装入背包的物品总效益最大 呢 并且总重量不能超过 M 如果 xi 只能取 0 或 1 也就是说一件物品要么装入全部 7 要么不装入 就是 0 1 背包问题 动态规划是解决多阶段决策过程的最优性原 它的目标就是要在所有容许选择的 决策序列中选取一个会获得问题最优解的决策序列 运用动态规划方法的前提是所求 解问题的最优性原理需成立 求解的关键是获取各阶段间的递推关系式 并且最优决 策序列具有如下性质 无论过程的初始状态和初始决策是什么 其余的决策都必须相 对于初始决策所产生的状态构成一个最优决策序列 动态规划方法建立在最优原则的 基础上 可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题 和 贪婪算法一样 在动态规划中可将一个问题的解决方案视为一系列决策的结果 不同 的是在贪婪算法中 每采用一次贪婪准则便做出一个不可撤回的决策 而在动态规划 中 还要考察每个最优决策序列中是否包含一个最优子序列 2 2 12 2 1 动态规划算法原理动态规划算法原理 1 动态规划算法基本思想 动态规划的基本思想就是将求解的较大问题一层一层地分解为较小的同类子问题 直到接求出子问题的解为止 可以直将待求解问题分解成若干个互相联系的阶段即子 问题 将各阶段按照一定的次序排列好之后 对于某个给定的阶段状态 先求解子问 题 然后从这些子问题的解的方法得到原问题的解 对于重复出现的子问题 只在第 一次遇到的时候对它进行求解 并把求得的解保存起来 让以后再次遇到时直接引用 已经求得的答案而不必重复计算 原问题的解依赖于所有大量的重复 而动态规划相 应的特点就是对于重复出现的子问题只在第一次遇到时加以求解 并把答案保存起来 让以后再遇到时直接引用不必重新求解 从而节省大量的计算时间 能采用动态规划求解的问题还需要满足一定的条件 1 最优化原理 如果问题的最优解所包含的子问题的解也是最优的 就称该问题 具有最优子结构 即满足最优化原理 2 无后效性 所谓的无后效性是指下一时刻的状态只与当前状态有关 而和当前 状态之前的状态无关 当前的状态是对以往决策的总结 3 有重叠子问题 也就是说子问题是不独立的 一个子问题在下一阶段决策中可 能被多次使用到 这个性质并不是动态规划适用的必要条件 但是如果该性质无法满 足 动态规划算法同其他算法相比就不具备优势 2 动态规划算法中的几个基本概念 l 动态规划 在多阶段决策问题中各阶段采取的决策 一般来说是和时间有关的 决策依赖于当前状态又随即引起状态的转移 一个决策序列就是在变化的状态中产生 出来的 这种解决多阶段决策最优化的过程称为动态规划 2 多阶段决策过程 有一类活动的过程由于它的特殊性 可以分成若干个互相联 系的阶段 在它的每一阶段都要做出决策 从而使整个过程达到最好的活动效果 这 种把一个问题看作是一个前后关联的具有链状结构的多阶段过程就成为多阶段决策过 程 3 最优化原理 一个最优化策略具有这样的性质 不论过去状态和决策如何 对 前面的决策所形成的状态而言 余下的决策必须构成最优策略 3 动态规划算法的适用条件 任何算法都有自己的适用性 超出了特定的条件它就失去了作用 同样动态规划 算法也不例外 动态规划算法通常用于解决具有某种最优性质的问题 在这类问题中 可能会有许多可行解 每一个解都对应一个值 我们希望找到具有最优值 最大值或最 小值 的那个解 也就是说适用动态规划算法的问题必须满足最优化原理和无后效性 8 根据最优化原理导出动态规划基本方程是解决一切动态规划问题的基本方法 4 算法设计 0 1 背包问题是一个符合最优化原理的无后效性且有重叠子问题特性的问题 我们 可以将 0 1 背包问题的求解过程看作是进行一系列的决策过程 即决定哪些物品该放 入背包 哪些物品不放入背包 设 fi X 表示背包容量为 X 时 i 个物品导致的最优解 的总价值 显然问题的最优价值为 fi M M 为背包的最大容量 根据动态规划的算法 思想 可以得到求解 0 1 背包问题的递归方程 fi X max fi 1 x fi 1 X wi pi 其中 i 代表第 i 次决策 0 i n X 代表剩余容量 0 X M X wi 表示装入物品 i 后背包的 剩余容量 fi 1 x 表示未装入物品 i 时的效益 fi 1 X wi pi 表示装入物品 i 后的效益 fi X 代表作出第 i 次决策后的效益值 2 2 在对 xi 作出决策之后 问题处于两种状态之 背包的剩余容量是 X 没有产生 任何效益 即 fi X fi 1 X 剩余容量是 X wi 效益值增长了 pi 即 fi X fi 1 X wi pi 当 fi 1 X fi 1 X wi pi 时 表示不装入物品 i 所得效益比装入物品 i 所得效益大 此时 fi X fi 1 X xi 0 反之 fi X fi 1 X wi pi xi 1 可见 确定装入物品 i 还是不 装入物品 i 的过程其实是比较 fi 1 X 与 fi 1 X wi pi 大小的过程 4 动态规划算法的基本步骤 设计一个标准的动态规划算法 通常可按以下几个步骤进行 1 划分阶段 按照问题的时间或空间特征把问题分为若干个阶段 注意这若干个 阶段一定要是有序的或者是可排序的 即无后向性 否则问题就无法用动态规划求解 2 选择状态 将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示 出来 当然状态的选择要满足无后效性 3 确定决策并写出状态转移方程 之所以把这两步放在一起 是因为决策和状态 转移有着天然的联系 状态转移就是根据上一阶段的状态和决策来导出本阶段的状态 所以 如果我们确定了决策 状态转移方程也就写出来了 但事实上 我们常常是反 过来做 根据相邻两段的各状态之间的关系来确定决策 4 写出规划方程 包括边界条件 动态规划的基本方程是规划方程的通用形式 化表达式 一般说来只要阶段 状态 决策和状态转移确定了 这一步还是比较简单 的 动态规划的主要难点在于理论上的设计 一旦设计完成实现部分就会非常简单 根据动态规划的基本方程可以直接递归计算最优值 但是一般将其改为递推计算 实 现的大体上的框架如下 标准动态规划的基本框架 对 fn 1 xn 1 初始化 边界条件 for k n k 1 k for 每一个 xk Xk for 每一个 uk Uk xk begin fk xk 一个极值 或 xk 1 Tk xk uk 状态转移方程 t fk 1 xk 1 vk xk uk 基本方程式 9 if t 比 fk xk 更优 then fk xk t 计算 fk xk 的最优值 end t 一个极值 或 for 每一个 x1 X1 do if f1 x1 比 t 更优 then t f1 x1 按照 10 式求出最优指标 输出 t 但是 实际应用当中经常不显式地按照上面步骤设计动态规划 而是按以下几个 步骤进行 1 分析最优解的性质 并刻划其结构特征 2 递归地定义最优值 3 以自底向上的方式或自顶向下的记忆化方法 备忘录法 计算出最优值 4 根据计算最优值时得到的信息 构造一个最优解 步骤 1 3 是动态规划算法的基本步骤 在只需要求出最优值的情形 步骤 4 可 以省略 若需要求出问题的一个最优解 则必须执行步骤 4 此时 在步骤 3 中计算 最优值时 通常需记录更多的信息 以便在步骤 4 中 根据所记录的信息 快速地构 造出一个最优解 2 2 22 2 2 0 10 1 背包问题最优性原理背包问题最优性原理 用 KNAPSACK 1 n M 表示 0 1 背包问题极大化 pixi 1 i n 约束条件 wixi X 1 i n xi 0 或 1 设 y1 y2 yn 分别是 x1 x2 xn 的 0 1 值的最优序列 若 y1 0 则 y2 y3 yn 必须相对于 KNAPSACK 2 n M 问题构成一个最优序列 如果不是 那么 y1 y2 yn 就不是 x1 x2 xn 的 0 1 值的最优序列 若 y1 1 则 y2 y3 yn 必须相对于 KNAPSACK 2 n M w1 问题构成一个最优序列 若不是则必有别的 0 1 序列 z2 z3 zn 满足 wizi M w1 z i n 且 pizi piyi 因此 序列 z1 z2 z3 zn 是一个对问题 KNAP SACK 1 n M 具有更大效益值的序列 也就是 说 最优性原理对 0 1 背包问题成立 1 最优子序列性质 在第一次决策之后 剩下的问题便是考虑背包容量为 r 时的决策 r c c w1 不管 xi 是 0 还是 1 x2 xn 必须是第一次决策之后的一个最优方案 如果不是则会 有一个更好的方案 y2 yn 因而 y1 y2 yn 是一个更好的方案 2 最优原则 principle of optimality 所谓最优原则即不管前面的策略如何 此后的决策必须是基于当前状态 由上一次 决策产生 的最优决策 3 动态规划递归方程 当最优决策序列中包含最优决策子序列时 可建立动态规划递归方程 它可以帮 助高效地解决问题 动态规划方法采用最优原则来建立用于计算最优解的递归式 假设 f i y 表示剩余容量为 y 剩余物品为 i i 1 n 时的最优解的值 即 2 3 由于对于有些问题的某些递归式来说并不一定能保证最优原则 因此在求解问题 时有必要对它进行验证 若不能保持最优原则 则不可应用动态规划方法 在得到最优 解的递归式之后 需要执行回溯以构造最优解 4 算法复杂度 10 当权为整数时 用二维数组 f 来保存各 f 的值 而回溯函数用于确定递归函数产 生的 xi 值复杂度为 O min nc 2n 动态规划算法是求解最优问题的一种高效率的算法 使用的原则是优化原则 即 整体的最优解可以通过局部的最优解获得 问题求解的过程可以概括成两句话 自顶 向下的分析 自下向上的计算 2 2 32 2 3 典型例题典型例题 0 1 背包问题是一个典型的动态规划问题 算法的证明过程比较复杂 但是计算过 程并不难理解 假设有这样的序列 n 3 M 6 物体数量为 3 背包能背的重量为 6 wi 2 3 4 物体重量 pi 1 2 5 物体的价值 初始化 Si P 待完成 代码 include stdio h include stdlib h define MAXSIZE 1000 void DKNAP int int int int void PARTS int int int int int int void main void Int i j n w p M if freopen input txt r stdin NULL Printf can t open file input txt n Exit 1 Scanf d Scanf d w int malloc sizeof int n p int malloc sizeof int n for i 0 i n i scanf d for i 0 i n i scanf d DKNAP w p n M void DKNAP int w int p int n int M int f l h k next u i j pp ww m int P MAXSIZE W MAXSIZE f int malloc sizeof int n 1 P 0 0 W 0 0 11 f 0 next 1 l h 0 for i 0 i M j u j for j l j u j ww W j w i pp P j p i while k h P next P k next k if k P k pp P k k if pp P next 1 P next pp W next ww next while k h while k 0 for j f i 1 j 0 printf d n i 2 2 42 2 4 动态规划向前处理法的递推过程动态规划向前处理法的递推过程 动态规划是一个多阶段决策过程 并且各个阶段是互相联系的 因此一般不可能 在每一阶段直接选出最优决策序列中属于此阶段的决策值 而动态规划的向前处理法 就是从最后阶段开始 以逐步向前递推的方式列出求前一阶段决策值的递推关系式 即根据 xi 1 Xn 的那些最优决策序列来列出求取 xi 决策值的关系式 列出关系式后 由最后阶段开始 回溯求解这些关系式得出最优决策序列即最优解 对 0 1 背包问题 设 gj X 是 KNAPSACK j 1 n X 最优解的值 显然 g0 M 是 KNAPSACK 1 n M 最优解的值 并且 xi 可能的取值是 0 或 1 故可得 g0 M max g1 M g1 M w1 p1 而 xj 取值也可能是 0 或 1 因此推出向前处理法求解背包问题的递推关系式如下 gj X max gj 1 X gj 1 X wj 1 pj 1 对 X 大于等于零的所有取值 有 gn X 0 若 X 小于零则有 gn X 以此背包问题 n 3 w1 w2 w3 2 3 4 p2 p3 p4 1 2 5 M 6 为例利用向前处 理法求解背包问题的递推关系式递推求解如下 G1 x 2 4 G2 x 2 5 13 G3 x 2 6 可得 g0 M max g1 M g1 M w1 p1 max 5 5 1 6 即背包问题的最优解为 6 然后再根据 gi 的取值情况就能够确定获得最优解的最优决策序列 因为 g0 M 6 是在 x1 1 的情况下取得的 故 x1 1 g0 M p1 5 而 g2 X 和 g1 X 都可取值 5 因 此 x2 0 g0 x 不能取值 5 故 x3 1 这样就得最优决策序列 x1 x2 x3 1 0 1 2 2 52 2 5 图解法求解背包图解法求解背包 把上题的求解过程用坐标图表示如下 左边一列给出函数 gj 1 X wj 1 pj 1 的图像 右边一列给出递推关系所得的函数 J 2 g3 X w3 p3 4 5 0 J gj 1 X wj 1 Pj 1 gj X G3 X 0 5 0 4 G2 X 图 2 1 背包问题的函数图像 可以看出 将 gj 1 X 在 X 坐标上右移 Wj 1 个单位 在 Y 坐标上上移 Pj 1 个单 位 得出 gj 1 X wj 1 pj 1 的函数曲线 gj X 是由 gj 1 X 和 gj 1 X wj 1 pj 1 的函 数曲线按照 X 相同时取最大值的规则归并而成 不仅形象直观 而且浅显易懂 14 7 7 0 Gj X 5 7 0 2 347 0 8 7 6 3 5679 j 0 g1 x w1 p1 8 7 6 5 2 0 34679 Go X 图 2 2 函数曲线图 可以看出 将 gj 1 X 在 X 坐标上右移 Wj 1 个单位 在 Y 坐标上上移 Pj 1 个单 位 得出 gj 1 X wj 1 pj 1 的函数曲线 gj X 是由 gj 1 X 和 gj 1 X wj 1 pj 1 的函 数曲线按照 X 相同时取最大值的规则归并而成 不仅形象直观 而且浅显易懂 2 2 62 2 6 多条件限制的多条件限制的 0 10 1 背包问题背包问题 1 问题描述 有 N N 100 件物品 每一件重量为 Weight i 价值为 V i 一个人有一个重量上 限为 W W 1000 的背包 他想拿走这 N 件物品的 K K N 件 使得拿走的物品总价值 最大 但同时拿走的物品必须把背包装满 问这个人应该拿哪 K 件物品 请输出这 K 件物品的编号 这个问题不是通常的 0 1 背包问题 因为它多了两个限制条件 1 必须选取 K 件 2 这 K 件物品的重量之和为 W 另外还要求输出具体的选取物品方案 但它还是 一个典型的动态规划问题 算法 A 设 F I j w 表示从物品 1 到物品 i 中 选取 j 件物品 使得总重量为 w 能够取得 的最大价值 不难得到动态规划方程如下 2 7 当输出具体方案时利用 反向追踪 从 F n k w 开始 若 F I j w F i 1 j w 说明没有选取第 i 件物品 记 i i 1 j j w w 若 F I j w F i 1 j 1 w weight i v i 说明选取了第 i 件物品 记 i i 1 j j 1 w w weight i 不断重复此过程 直到 i 0 为止 就求出了选取方案 此算法时间复杂度为 O N K W 而空间复杂度为 O N 2 W 如果每个元素为 J 1 g2 X w2 p2 15 Longint 的话 这样的静态数组将耗费 100 100 1000 4 Byte 4 10 7 Byte 空间耗费极 大 算法 B 设 1 F I j 表示选 I 件物品 它们的重量和为 j 能够取得的最大价值 2 P I j 表示选 I 件物品 它们的重量和为 j 达到最大值价值时选取的最后一 件物品的编号 这个数组用于记录方案 首先处理只取一件物品的情况 2 8 然后处理选取 2 3 K 件物品的情况 我们采用顺推的方法 For i 1 to K 1 do For j 1 to W do Begin If F I j 说明存在 F I j 这个状态 于是扩展此状态 11 I 12 j while l1 0 do begin Onthepath P l1 l2 True dec l1 dec l2 weight P l1 l2 end 这一部分是该算法最重要的环节 算法 B 利用 P 数组储存的信息 从后往前检查 整条到达 F i j 状态的决策路径 将路径上的所有决策都进行标记 Onthepath I True 时 表示在到达状态 F i j 的选取方案中包含物品 I For kk 1 to N do 枚举每一件物品 KK If F I j v k k F i 1 j weight k k and NotOnthepath k k then Begin 如果 kk 不在到达 f i j 的决策路径上 说明未选取过物品 k k F i 1 j weight k k F i j v k k P i 1 j weight k k kk 选取 kk End End 当上述过程结束以后就求得了最大价值 下面构造选取方案 设 Use 数组表示物品 I 是否被选取 从 F K W 开始反向追踪 Use P K W True 记 W W weight P K W K K 1 继续上述过程 直到 K 0 为止 就得到了 Use 数组的值 问题解决 该算法时间复杂度仍为 O N K W 但空间复杂度为 O N W 如果数组的每个 元素为 Longint 则静态数组将耗费 100 1000 4 Byte 4 10 5 Byte 2 编程任务 给定电路板 xoy 坐标系 以及电路板上 n 个关键逻辑元在 xoy 坐标系中按照 2 维 降序排列的位置 xl yl x2 y2 xn vn 其中 16 1 3000 0 x1 x2 xn 20000 0 yn yn 1 y1 20000 编程计算以 n 个关键逻辑元为叶结点的正交树中 总边长最小的最优正交树 y x 5 54321 4 3 2 1 图 2 3 达尔文芯片正交树图 3 问题分析 注意到题目中条件 个关键逻辑元在 xoy 坐标系中按照 2 维降序排列 该问题 表面上是二维问题 而实际上是一维问题 线性模型的问题一般有两种分析思路 l 把线性结构分成两部分 用递归的思路来分析问题 2 在最优集中每次增加一个元素 逐步扩大考虑范围 用递推的思路来分析问题 下面分析最优子结构 思路 l 将 i 到 j 点的总边长最小的正交树找一点 k 分成两个部分 而为了能分成 两个部分 k 点是枝平行 x 轴的点或 i 点且 k l 点必是枝平行 y 轴的点或 j 点 事实上 用 k 分割后的得到的两个子正交树必均取得最小值 否则可以用更小的值替换这两个 子正交树 与 i 到 j 点的正交树取最小值矛盾 所以该问题满足最优子结构性质 思路 2 即用多阶段决策建立模型 要添加的的 k 点要么取平行 轴方向的枝 要 么取平行 y 轴方向的枝 但是一旦添加进去 1 个点对后面要添加的点产生影响 导致 后面要添加的点不能有 x 轴或 y 轴方向的枝 所以这种决策法具有 后效性 要使得 它具有最优子结构 就要消除这种后效性 需要在一个状态中添加多个维数才能消除 表达最优子结构所需的参数 由于采用思路 1 需要两个参数 起始点位里 i 和终结点 的位 j 建立递归表达式 mli jl 表示从 i 点到 j 点最优的正交树的边长和 2 9 4 算法实现 动态规划法有两种实现方式 即自顶向下的递归和自底向上的递推 递归法很灵 活 它可以采用自顶向下的 剪枝 跳过计算一些无用的值 结合记忆化搜索来加速 递推法则按照一定次序从已知推未知 可采用滚动数组等减少空间消耗 四边形不等 式等降低时间复杂度 本题如果采用递归法从顶部无法确定要进行那些 剪枝 空间 也无法节省 而递推实现都能优化 所以本题较适合用递推法 空间复杂度 在二维表中有 O n2 项要计算 算新的对角线上的值时 算过的值都 可能要用到不能侧除 所以算法的空间复杂度为 0 nZ 时间复杂度 注惫到本题可以用四边形不等式 时间复杂度可降到 0 nZ 设计动 17 态规划主要难点是找到最优子结构 并选择合适的维度 方式刻划最优子结构 建立 递归表达式 设计一般两种思路 递归思路和多阶段决策的递推思路实 递归法 应用自顶向下的 剪枝 记忆化搜索来加速和节省空间 递推法 可采 用滚动数组等减少空间消耗 用四边形不等式 状态合理组织等方法降低时间复杂度 2 2 72 2 7 动态规划的程序代码动态规划的程序代码 这是头文件 knapsack hpp ifndef KNAPSACK HPP define KNAPSACK HPP using namespace std const int MAX COUNT OF WIDGETS 16 const int MAX CAPACITY OF KNAPSACK 15 int CAPACITY OF KNAPSACK 0 int COUNT OF WIDGETS 0 This struct widget is defined struct Widget int m iID int m iVolume int m iValue bool m bSelected This struct knapsack is defined struct Knapsack int m iCapacity int m iValue This struct will be used in DynamicPrograming m iMaxValue indicates the maximum value can be achieved when the count of widgets is i and the capacity of the knapsack is j m bSelected indicates to achieve the maximum value whether the i th widget is selected under the same condition stated above struct MemeorizeMark int m iMaxValue bool m bSelected class SolveKnapsack public bool Init bool DynamicProgramming 18 void PrintMaxValue const void PrintSelection const private Knapsack m Knapsack Widget m Widget MAX COUNT OF WIDGETS int m iCountOfWidgets MemeorizeMark m MemeorizeMark MAX COUNT OF WIDGETS MAX CAPACITY OF KNAPSACK endif 这是 cpp 文件 knapsack cpp include include knapsack hpp using namespace std bool SolveKnapsack Init initialize the knapsack cout Pls input the capacity of knapsack 0 capacity MAX CAPACITY OF KN KNAPSACK m Knapsack m iCapacity m Knapsack m iCapacity 1 if 0 m Knapsack m iCapacit