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

科技前沿 • 2025-01-27 08:28 • 阅读 35

大家好，我是讯享网，很高兴认识大家。

动态规划

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

挖金矿问题与分析

5座金矿，每座金矿的黄金储量不同，需要参与挖掘的工人数也不同；参与挖矿的工人总数是10人；每座金矿要么全挖，要么不挖，不能派一半人挖一半金矿；若要尽可能多地挖取金矿，则怎么选择金矿？
金矿1： 200金/3人
金矿2： 300金/4人
金矿3： 350金/3人
金矿4： 400金/5人
金矿5： 500金/5人

讯享网

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

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

当人数不足以挖金矿时，只能获得 0 黄金，也是动态规划的边界
当人数只能够挖一座金矿时，选择最大黄金数的金矿
当人数足够挖两个金矿时，选择是挖一座黄金量多的黄金，还是挖两座黄金量少的黄金
以此类推

示例代码

Python

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 = 10 ans = 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]; } }

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

动态规划

挖金矿问题与分析

示例代码

相关推荐