动态规划之挖金矿问题（Python and Java）

动态规划

动态规划与 分治策略 很类似，都是将一个原问题分解为若干规模较小的子问题，递归的解决这些子问题，然后合并子问题的解得到原问题的解

两者区别在于，分治策略解决的问题中，各个子问题通常是相互独立的，但是动态规划中的各个子问题通常是有重叠的，当针对一个子问题的解求出后，可以将其记忆化储存

之前有讲过 动态规划之背包问题 ，这里是另一个比较经典的问题——挖金矿

挖金矿问题与分析

5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同；参与挖矿的工人总数是10人；每座金矿要么全挖，要么不挖，不能派一半人挖一半金矿；若要尽可能多地挖取金矿，则怎么选择金矿？

金矿1： 200金/3人

金矿2： 300金/4人

金矿3： 350金/3人

金矿4： 400金/5人

金矿5： 500金/5人

为了理清思路，可以先先之前 动态规划之背包问题 中的分析一样，做出动态规划的表格，其中的具体分析都可以参考背包问题中的分析

考虑只有一个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量考虑只有两个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量考虑只有三个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量考虑只有四个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量考虑具有五个金矿时，工人数从1个到10个的递增过程中，可以获得的黄金的数量

当人数不足以挖金矿时，只能获得 0 黄金，也是动态规划的边界

当人数只能够挖一座金矿时，选择最大黄金数的金矿

当人数足够挖两个金矿时，选择是挖一座黄金量多的黄金，还是挖两座黄金量少的黄金

以此类推

示例代码

def get_gold(golds, ores, num_man):num_ore = len(ores)# 为了方便计算，多开辟了一行、一列dp = [[0 for i in range(num_man+1)] for _ in range(num_ore+1)]for i in range(1, num_ore+1):for j in range(1, num_man+1):if j < ores[i-1]:dp[i][j] = dp[i-1][j]else:dp[i][j] = max(dp[i-1][j], dp[i-1][j-ores[i-1]] + golds[i-1])return dp[num_ore][num_man]golds = [200, 300, 350, 400, 500]ores = [3, 4, 3, 5, 5]num_man = 10ans = get_gold(golds, ores, num_man)

Java

public class GoldMain {public static void main(String[] args) {int[] golds = {200, 300, 350, 400, 500};int[] ores = {3, 4, 3, 5, 5};int manNum = 10;int result = getGold(golds, ores, manNum);System.out.println(result);}// golds 表示金矿含金量，ores 表示挖矿需要人数，manNUm 表示总人数public static int getGold(int[] golds, int[] ores, int manNum) {int oLen = ores.length;// dp[i][j] 表示有 oLen 个金矿，manNum 人数时可以获得黄金量int[][] dp = new int[oLen + 1][manNum + 1];for (int i = 1; i < oLen+1; i++) {for (int j = 1; j < manNum+1; j++) {if (j < ores[i-1]) {dp[i][j] = dp[i-1][j];} else {dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-ores[i-1]] + golds[i-1]);}}}return dp[oLen][manNum];}}