背包与树形_黄哲威.pdf

【背包问题】是一种经典的动态规划问题，主要分为01背包问题和完全背包问题。01背包问题中，我们面临N件物品和一个容量为V的背包。每件物品占用空间Ci，对应价值Wi。目标是选择物品使得放入背包中的价值总和最大，但不能超出背包的容量限制。这个问题是NP完全问题，意味着没有已知的多项式时间解决方案。 在01背包问题中，定义状态转移方程为F[i, v]，表示前i件物品在容量为v的背包中能获得的最大价值。方程表示为： F[i, v] = max{F[i - 1, v], F[i - 1, v - Ci] + Wi} 这个方程说明了第i次决策时，我们可以选择放或者不放第i件物品。如果不放，则问题归结为仅考虑前i - 1件物品的子问题，价值为F[i - 1, v]；如果放第i件物品，背包剩余容量为v - Ci，这时的最大价值是F[i - 1, v - Ci]加上第i件物品的价值Wi。 为了优化存储，我们希望使用一维数组来解决问题。在计算F[i, v]时，需要保证可以访问到F[i - 1, v]和F[i - 1, v - Ci]的值。这意味着我们需要按照某种顺序遍历状态数组，确保之前的状态已经被计算过。 完全背包问题与01背包类似，区别在于每种物品无限供应。因此，对于每种物品，不仅可以选择放或者不放，还可以选择放任意多件。这会导致状态转移方程有所不同，可能需要考虑更多物品数量的组合情况。 树形动态规划通常涉及树结构的数据操作，包括树的存储方式、遍历算法（如深度优先搜索DFS和广度优先搜索BFS）以及树的信息统计。在树上进行动态规划时，可能会涉及到树的递推关系，例如计算路径和、节点深度、子树信息等，同时需要掌握一些处理技巧，以有效地解决树结构中的优化问题。 在实际应用中，背包问题和树形动态规划常用于互联网领域的资源分配、任务调度、数据结构优化等问题。通过动态规划和树形结构，我们可以设计出高效的算法，解决复杂的问题，提高系统性能。在学习和解决这些问题时，理解和掌握动态规划的思想、状态转移方程以及树的特性是非常重要的。