闫式Dp分析法（一种求解动态规划问题的思路）

2023-12-21 22:55:57

? ? ? ? 最近一直跟着Acwing学习动态规划问题的求解思想，感觉晦涩的算法问题一旦经过闫式Dp分析法的剖析，瞬时迎刃而解，故今天我觉得很有必要再次分享一下闫式Dp分析法（在此默认你对DP问题有了一定的了解）。

闫式Dp分析法

????????闫式Dp分析法包含了问题的状态表示与状态的计算，其中状态表示又可以细分为集合的定义以及集合的属性，而动态规划问题的最终答案就是最终所求集合的属性。

? ? ?

? ? ? ? 总所周知，解决DP问题一般需要定义一个二维数组f,而f的每一项f(i,j)在闫式Dp分析法中蕴含着丰富的意义。其中，集合的定义与坐标i与j之间存在直接联系，而f(i,j)的值就是该集合的属性。状态的计算脱离不了集合的划分，其中f(i,j)对应的集合set将会划分为若干个子集合set_{i}，其中

????????set = \bigcup (set_{i}) \; \; and \; set_{i} \bigcap set_{j} = \emptyset \; (i!=j)

? ? ? ? 概念都是抽象的，下面我举出一个经典的Dp入门问题01背包问题的案例，并借助闫式Dp分析法解决它，以便让读者有更加深刻的理解.

案例分析

? ? ? ? 在阅读下面案例分析内容时，默认读者已对问题有基本了解，不再做任何问题的描述.

01背包问题

? ? ? ? 01背包问题给出N件物品何一个容量为V的背包，在每一件物品都只能使用一次的情况下，考虑一种物品的装载方案，求算出容量为V的背包所能装载物品的最大价值（每一个物品都有一个对应的价值和体积）.

? ? ? ? 直接定义二维数组f,那么我们可以这样子定义状态的表示，其中f(i,j)状态对应的集合含义为：在只考虑选择前i个物品的情况下，将前i个物品中的若干个装入背包，使其容量之和小于或等于j的所有方案.该集合的数学表示为：set = \{set_1,set_2,...,set_{i},...\}.

? ? ? ? 其中set_{i}表示其中一种物品装入背包的方案，与此同时，假设obj_{i},v_{i}分别表示第i物品与第i个物品的体积，那么任意一个set_{i} = \{obj_{k}|1<=k \; and \; k<=i \; and \sum_{k=1}^{i}(v_{k})<=j \}.

? ? ? ? f(i,j)表示集合某一个属性，在01背包问题中，f(i,j)表示集合中某一个元素中所有物品之和的最大值。看起来有点抽象，但是f(i,j)有如下数学公式,其中m_{k}表示第k个物品的价值：????????????????? ? ? ? ? ? ? ? ? ? ? ? ??f(i,j) = max \sum m_{k},m_{k} \in set_{i}

? ? ? ? 最后，我们来划分一下f(i,j)对应的集合，其实很简单。由于每一个物品只能选一次，只存在选与不选两种方案，因此集合可以划分为set_{k}包含第i个物品或者set_{k}不包含第i个物品.f(i,j)表示集合中某一个元素中所有物品之和的最大值,因此f(i,j)的推导公式如下：f(i,j) = max(f(i-1,j),f(i-1,j-v_{i})+m_{i})

? ? ? ? 最后，01背包问题的最终答案就是f(N,V)!

? ? ? ? 好了，01背包问题的闫式Dp分析法到此为止便结束了，还有更多的DP问题都能够通过闫式Dp分析法来解决。毕竟，闫式Dp分析法在大部分情况下还是很好用的，它的难点在于如何定义集合，要求集合与二维数值下标(i,j)建立起联系，与此同时要定义集合的属性，属性往往与问题的答案相互挂钩，最后是将集合划分，推算出集合属性与它的子集合属性之间的数学公式，建立起递推方程.

写在最后

? ? ? ? 阅读完上述的闫式Dp分析法后，倘若你有所领悟，你便能发现动态规划之所以省时间的原因是，它优化了暴力解决方法。

? ? ? ? 倘若使用暴力方法求解背包问题，那么由于一共有2^{N}种物品的组合方案（每种物品有选与不选两种选择）,对于每一个方案需要求算它的体积之和以及价值之和，那么总共的时间复杂度为O(N*2^{N}).这个是一个很糟糕的时间复杂度，即使N = 1000，暴力解法的计算次数已经高达10^{303}次。一般电脑C++每秒求算10^{7}~10^{8},

即该问题基于暴力解法的最好求算时间是10^{295}秒，大概是10^{280}亿年！！！是不是大为震撼，地球诞辰以来还不需要如此长的时间，倘若真的使用暴力解法来求算背包问题，恐怕要计算到宇宙爆炸，你的生命等不来，甚至连人类社会都等不来，哈哈！然而，倘若使用动态规划算法来求解，只需要1s,两种算法之间需要存在天壤之别！

? ? ? ? 之所以举出上述对比案例，并非平白无故，是为了让你能够感受到动态规划算法的威力，让你艰辛的动态规划算法的学习之旅不再枯燥，你将带着一种仰望的姿态来学习这种优美的、威力十足的算法！

文章来源:https://blog.csdn.net/m0_72579201/article/details/135139056
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。