动态规划算法02

算法02"/>

动态规划算法02

矿工挖矿问题

矿工挖矿

问题描述

该问题为了解决在给定金矿和矿工数量的前提下，能够获得最多黄金的挖矿策略。很多算法题其实就是这个问题换了一个情境。

有5个金矿，每个金矿黄金储量不同，需要参与挖掘的工人数目也不同，假定有10个工人，每个金矿要么全挖，要么不挖，不可以拆分，试问，想得到最多的黄金，应该选择挖取哪几个金矿。金矿信息如下表。

题解思路

如果要使用动态规划解题，就要确定动态规划的三要素：最优子结构、边界和状态转移函数。

最优子结构

解题目标是确定10个工人挖5个金矿能够获得最多的黄金量，该问题可以从10个工人挖4个金矿的子问题中递归求解。而我们在解决10个工人挖4个金矿时，存在两种选择，一种是放弃第5个矿，将10个工人投入到挖四个矿中；另一种选择是决定对第5个矿进行挖掘，因此需要从这10个人中抽取3个人（第5个矿需要人数）加入第5个矿开采，剩余的人处理前4个矿。因此，最优解应该是这两种选择中获得黄金数量较多的那一种。

为了描述方便，设金矿数量为 n n n，工人个数为 w w w，第n个矿的黄金数量为 G [ n − 1 ] G[n-1] G[n−1],第n个矿所需工人为 P ( n ) P(n) P(n)，要想获得10个矿工挖掘5个金矿的最优解为 m a x ( F ( 4 , 10 ) , F ( 4 , 10 − P [ 4 ] ) + G [ 4 ] ) max(F(4,10),F(4,10-P[4])+G[4]) max(F(4,10),F(4,10−P[4])+G[4])。这就是最优子结构。

边界

对于第一个金矿而言，若当前的矿工数量不能达到金矿的挖掘需要则只能放弃这个矿，获得的黄金数量为0；若能满足矿工数量要求，获得的黄金数量为 G [ 0 ] G[0] G[0]。
因此，边界可以描述为

• n = 1 , w > = P [ 0 ] n=1,w>=P[0] n=1,w>=P[0]时， F ( n , w ) = G [ 0 ] F(n,w)=G[0] F(n,w)=G[0]
• n = 1 , w < P [ 0 ] n=1,w<P[0] n=1,w<P[0]时， F ( n , w ) = 0 F(n,w)=0 F(n,w)=0

状态转移函数

F ( n , w ) = { 0 ( n < = 1 , w < P [ 0 ] ) G [ 0 ] ( n = = 1 , w > = P [ 0 ] ) F ( n − 1 , w ) ( n > 1 , w < P [ n − 1 ] ) m a x ( F ( n − 1 , w ) , F ( n − 1 , w − P [ n − 1 ] ) + G [ n − 1 ] ) ( n > 1 , w > = P [ n − 1 ] ) F(n,w) = \left\{ \begin{aligned} & 0 &(n<=1,w<P[0]) \\ & G[0] &(n==1, w>=P[0])\\ & F(n-1,w) & (n>1,w<P[n-1])\\ & max(F(n-1,w), F(n-1, w-P[n-1])+G[n-1]) &(n>1,w>=P[n-1]) \end{aligned} \right. F(n,w)=⎩ ⎨ ⎧​​0G[0]F(n−1,w)max(F(n−1,w),F(n−1,w−P[n−1])+G[n−1])​(n<=1,w<P[0])(n==1,w>=P[0])(n>1,w<P[n−1])(n>1,w>=P[n−1])​

到这里，三要素找到了，经过这个过程也明白了求解过程，由底向上计算，一步步推导可以得到结果，换句话说，n步的解其实就是第一步的结果推来的。

首先，我们可以使用递归的方法来写，它是自顶而下的。

def gold_mining(n ,w, G, P):if n <= 1 and w < P[0]:return 0if n == 1 and w >= P[0]:return G[0]if n > 1 and w < P[n-1]:return gold_mining(n-1, w, G, P)if n > 1 and w >= P[n-1]:return max(gold_mining(n-1, w, G, P), gold_mining(n-1, w-P[n-1], G, P) + G[n-1])if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

这个解法可以求得最优解，会以树形结构求解子问题，如下图所示，不难发现，若金矿有 n n n和，工人充足，复杂度即为 O ( 2 n ) O(2^n) O(2n)。

优化思路

当金矿只有5个的时候，问题不是很复杂，但是当金矿数目增加的时候，这样的复杂度是无法接受的，直观上来看，这种递归之所以慢其实是因为进行了如下图所示的重复计算。

事实上，我们可以通过维护DP Table的方式来存储最优解从而以自下而上的方式求解本题，表格中的dp[i][j]就表示F(n,w)的值，因此我们可以得到如下的代码。

def gold_mining(n ,w, G, P):dp = [[0] * (w+1) for _ in range(len(G)+1)]for i in range(1, len(G)+1):for j in range(1, w+1):if j < P[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-P[i-1]] + G[i-1])return dp[len(G)][w]if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

上述代码的时间复杂度和空间复杂度都是 O ( n w ) O(nw) O(nw)，这比递归的性能好了很多。

进一步优化

上面这段代码其实时间上已经没什么优化的空间了，空间上还可以进一步优化。我们不妨回顾DP表，可以发现，其实每一行的结果值依赖于上一行的10个结果。举个例子，我们已4个金矿9个工人为例， F ( 4 , 9 ) F(4, 9) F(4,9)来源于 F ( 3 , 5 ) F(3,5) F(3,5)和 F ( 3 , 9 ) F(3,9) F(3,9)，这两个结果显然在上一行已经计算了。

因此，其实无论金矿多少个，我们也只需要保存一行的数据，在下一行计算时，从右向左统计并更新数据即可。

优化后的代码如下，可以发现，空间复杂度降低到了 O ( n ) O(n) O(n)，这就是本题的最优方法了。

def gold_mining(n ,w, G, P):dp = [0] * (w+1)for i in range(1, len(G)+1):for j in range(w, 0, -1):if j >= P[i-1]:dp[j] = max(dp[j], dp[j-P[i-1]] + G[i-1])return dp[w]if __name__ == '__main__':G = [400, 500, 200, 300, 350]P = [5, 5, 3, 4, 3]n = 5w = 10print(gold_mining(n, w, G, P))

补充说明

具体代码可以查看我的Github，欢迎Star或者Fork，参考书《你也能看得懂的Python算法书》，书中略微有一点不合理之处，做了修改。到这里，其实你已经体会到了动态规划的简约之美，当然，要注意Python是有递归深度限制的，如不是必要，建议使用循环控制。