The Gold Mine Problem
Problem Statement
Given a gold mine of n*m dimensions, each cell in this mine contains a positive integer which is the amount of gold in tons. Initially, the miner is at the first column but can be at any row. He can move only right, diagonally right and up, or diagonally right and down. from the current cell. Find out the maximum amount of gold he can collect.
Before diving into the problem, let us first look into the concept of two problem solving techniques, called the Greedy Approach and the Dynamic Programming Approach.
Greedy approach:
The greedy approach is considered one of the most straightforward approach which can be applied to a variety of problems. Most of these problems have n inputs and require us to obtain a subset that satisfies some constraints/conditions. A subset which satisfies the constraints is called a feasible solution. Our main goal is to find a feasible solution that either maximizes or minimizes an objective function. A feasible solution that does this is an optimal solution. Usually, the feasible solutions are derived quite easily but that is not always the case for the optimal solutions.
The greedy approach suggests an algorithm that works in stages, considering one input/step at a time. At each and every stage, a decision is made whether a particular input gives the optimal solution or not. This is done by considering inputs in an order determined by some selection procedure. The selection procedure is also based on some optimization measure. If inclusion of next input into the partially constructed optimal solution will result in an infeasible solution, it is not added to the solution set. Else, it is added.
Now that we have an idea about the greedy approach, let us go ahead and look into the dynamic programming approach.
Dynamic Programming:
This approach is an algorithm design method used when the solution to a problem can be viewed as a result of sequence of subproblems/decisions. It solves problems by combining solutions to subproblems. It is usually applied when subproblems overlap, i.e. when subproblems share subsubproblems.
It is different from the divide and conquer approach as divide and conquer does more work than necessary by repeatedly solving the common subsubproblems whereas in the case of dynamic programming, the subsubproblems are computed only once and their solutions are stored in a table, avoiding the re-computation of the subsubproblems every time.
Approach to Gold Mining Problem
So, when you think about the problem after looking at the above two approaches, it seems simple enough, right? We need the maximum gold that can be acquired, so applying the greedy approach should do the trick.
Let’s try to test it with an example!
Take a look at this example. According to the rules of the gold mining problem, the miner can be at any row but should be at the first column.
So, now that we are testing the greedy approach, we should select the maximum element in the 1st column, which is 3 located at (2,0).
After we take 3, we can either take 6(diagonally above to the right) or 0(to the right). As 6>0, we take 6.
Now, we can either go to the 4(diagonally above to the right), the other 4(to the right), or the 0(diagonally right). As 4>0, we can take either of the 4’s(both are correct).
The final solution achieved is: 3+6+4=13
We then check all other possible solutions to confirm our answer using the Brute Force Approach.
The Brute Force Approach or exhaustive search approach, is a very general problem-solving technique that consists of systematically enumerating all possible solutions and checking whether each candidate satisfies the problem’s statement.
So, when we check out all the possible solutions, we see that the maximum solution that can be arrived is 2+5+12 = 19
But there was no way in which we could’ve arrived at this solution using the greedy approach.
So, we arrive at the conclusion that this problem can’t be solved using Greedy approach and we need to use the dynamic programming approach.
Dynamic Approach solution
To solve this problem, we have to keep computing the value of maximum gold at each cell and update them in a table every time.
If we are given a matrix of dimension x*y , Gold_Mine [x][y],we begin by creating a matrix of same dimension Max_Gold[x][y]
Initialization :
We initialize each cell except cells in the 1st column to 0. The cells in the 1st column already have the maximum gold that can be taken. So, it would be:
#for the 1st columnfor i from 0 to y-1Max_Gold[i][0]=Gold_Mine[i][0];
Step 2
After initialization, for the remaining cells, we take each cell (column-wise) and compute the maximum gold that the miner can achieve by standing at that particular cell.
Max_Gold[i][j] = Gold_Mine[i][j] + max { Max_Gold[i],[j-1] , Max_Gold[i-1],[j-1] , Max_Gold[i+1],[j-1] } for all possible values
For the 2nd column:
When we apply the formula,
Max_Gold[0][1] = Gold_Mine[0][1] + max { Max_Gold[0],[0] , Max_Gold[-1],[0] (not possible) , Max_Gold[1],[0] }
Substituting values:
Max_Gold[0][1] = 5+ max { 1 ,2}
= 5+2
= 7
Max_Gold[1][1]= 4+max{1,2,0}
= 4+2
=6
Same way, after calculating values for each cell in 2nd column, the updated table would look like:
For the 3rd column:
After computing values for 3rd column after applying the formula, the final table would look like:
Now, the last step is to search through the entire last column and pick the maximum value in it. That value will give us the maximum amount of gold that can be mined by the miner.
In this case, as 19 is the maximum cost in the last column, it is the maximum amount of gold that can be mined.
Implementation of the above approach(C++) :
#include <bits/stdc++.h>
using namespace std;
int GoldMine(int** Gold_Mine, int rows, int columns)
{
//creating the table for updated values
int max_gold[rows][columns];
memset(max_gold, 0, sizeof(max_gold));
for (int i = 0; i < rows; i++)
max_gold[i][0] = Gold_Mine[i][0];
//traversing columns one by one
for (int j = 1; j < columns; j++) {
for (int i = 0; i < rows; i++) {
//original value of cell
max_gold[i][j] = Gold_Mine[i][j];
//temporary variable 'temp' to find maximum out of possible moves
int temp = max_gold[i][j - 1]; //cell to immediate left
if (i - 1 >= 0) { //if there exists a row above,
if (temp < max_gold[i - 1][j - 1]) //compare immediate left to
//left upper diagonal
temp = max_gold[i - 1][j - 1];
}
if (i + 1 < rows) { //if there exists a row below,
if (temp < max_gold[i + 1][j - 1]) //compare immediate left to
//left lower diagonal
temp = max_gold[i + 1][j - 1];
}
max_gold[i][j] += temp; //add maximum of immediate left,
//left upper diagonal or left
//lower diagonal to original value of cell
}
}
// selecting maximum from the last column
int gold = max_gold[0][columns - 1];
for (int i = 1; i < rows; i++) {
if (max_gold[i][columns - 1] > gold)
gold = max_gold[i][columns - 1];
}
return gold;
}
int main()
{
int rows, item, columns;
cout<<"\t\t\t\t********Gold Mine Problem Implementation********\t\t\t\t\t"<<endl;
cout << "Enter the number of rows : ";
cin >> rows;
cout << "Enter the number of columns : ";
cin >> columns;
cout << "Enter values of the matrix row-wise : \n";
cout<<"------------------------------------------------"<<endl;
int** Gold_Mine = (int**)(malloc(sizeof(int*) * rows));
//Taking input of matrix cells
for (int j = 0; j < rows; j++) {
Gold_Mine[j] = (int*)(malloc(sizeof(int) * columns));
for (int k = 0; k < columns; k++)
{
cout<<"Enter matrix value at position ("<<j<<","<<k<<"): ";
cin >> Gold_Mine[j][k];
}
}
cout << "\n\nMax amount of gold that can be collected by the miner is: " << GoldMine(Gold_Mine, rows, columns) << " units "<<endl;
return 0;
}
References:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001, Unit 16.
- Horowitz and Sahani, Fundamentals of Computer Algorithms, 2ND Edition , Unit 4
- https://www.includehelp.com/icp/gold-mine-problem.aspx