背包问题之动态规划法PPT学习教案.pptx

【动态规划法】是解决复杂优化问题的一种有效方法，尤其在面对具有重叠子问题和无后效性特征的问题时，如本文件中提到的【背包问题】和【多段图的最短路径问题】。动态规划的核心在于通过构建一个二维数组或表格，将原问题分解为多个相互关联的子问题，并按顺序逐个解决，最终得到原问题的最优解。 1. **概述**： - 动态规划是一种通过逐步构建最优解来解决最优化问题的策略。 - 它适合处理具有多个阶段、每个阶段都有多个决策，并且前一阶段的决策会影响后续阶段的问题。 2. **什么是动态规划**： - 动态规划是一种算法设计技术，它通过对问题进行分治，将大问题分解为小问题的子集，然后逐个解决这些子问题，存储中间结果，避免重复计算，以达到找到全局最优解的目的。 3. **最优性原理**： - 在有向加权图的最短路径问题中，动态规划方法基于最优子结构的性质，即一条最短路径的任意子路径也必须是最短的。若存在反例，即最短路径中的一段子路径不是最优的，那么可以构造出更短的总路径，这与最短路径的定义矛盾。 4. **无后效性原则**： - 在动态规划中，一个决策一旦做出，不会影响之前已经做出的决策，即当前决策只依赖于之前的状态，而不受之后决策的影响。这对于构建状态转移方程至关重要。 5. **背包问题**： - 背包问题是一种经典的组合优化问题，通常包括0-1背包、完全背包和多重背包等类型，目标是在容量限制下使装入物品的总价值最大。 6. **多段图的最短路径问题**： - 多段图是一种特殊的有向图，其顶点被划分为多个互不相交的子集，每一段内部的顶点不相邻。动态规划可以通过构建状态转移方程求解从源点到终点的最小代价路径。 - 状态通常表示为`d(i, j)`，表示从顶点i到顶点j的最短路径，通过比较所有可能的路径来更新这个值。 7. **状态转移方程**： - 在多段图的例子中，`d(i, j)`的计算依赖于前面阶段的`d(k, l)`，例如`d(0, 9)`通过`d(1, 9)`, `d(2, 9)`, `d(3, 9)`的最小值来确定，依次类推，直到最终找到从源点到终点的最短路径。 8. **决策过程**： - 通过一系列的决策，如`d(6, 9)`依赖于`d(7, 9)`和`d(8, 9)`，并结合边的权值计算得出，最终得到从源点到终点的最优路径。 总结来说，动态规划法是解决多阶段决策问题的强大工具，它在背包问题和多段图最短路径等场景下表现出色，通过构建状态转移方程并利用最优性和无后效性，能够有效地找到全局最优解。在实际应用中，如物流路径规划、资源分配等问题中，动态规划都有着广泛的应用。