Dynamic Programming Solution for the Gold Mining (Knapsack) Problem

Problem description: given five gold mines with different gold amounts and required workers, and ten workers total, select mines to maximize gold without splitting any mine.

Analysis: The problem is equivalent to a 0/1 knapsack problem and can be solved using dynamic programming by constructing a DP table where rows represent mines and columns represent possible worker counts.

Implementation: Python functions are provided to build the DP table and backtrack the selected mines. def mine(count, TotalWorkers, workers, gold): # initialize DP table reserves = [[0 for j in range(TotalWorkers + 1)] for i in range(count + 1)] for i in range(1, count + 1): for j in range(1, TotalWorkers + 1): reserves[i][j] = reserves[i - 1][j] if j >= workers[i - 1] and reserves[i][j] < reserves[i - 1][j - workers[i - 1]] + gold[i - 1]: reserves[i][j] = reserves[i - 1][j - workers[i - 1]] + gold[i - 1] for x in reserves: print(x) return reserves def show(count, TotalWorkers, workers, reserves): x = [False for i in range(count)] j = TotalWorkers for i in range(count, 0, -1): if reserves[i][j] > reserves[i - 1][j]: x[i - 1] = True j -= workers[i - 1] print('可挖最大存储量为:', reserves[count][TotalWorkers]) print('要挖的金矿为:') for i in range(count): if x[i]: print('第', i + 1, '个矿', end='') # Example usage count = 5 TotalWorkers = 10 workers = [5,5,3,4,3] gold = [400,500,200,300,350] reserves = mine(count, TotalWorkers, workers, gold) show(count, TotalWorkers, workers, reserves)

Result: For the given data (workers = [5,5,3,4,3], gold = [400,500,200,300,350], TotalWorkers = 10) the algorithm finds the maximum extractable gold of 900 kg by selecting the first and second mines (400 kg and 500 kg).