Gold Mine Problem
The Gold Mine Problem is a classic dynamic programming problem where we are given a 2D matrix representing a gold mine. Each cell in the matrix contains a certain amount of gold. The objective is to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column. In this article, we will explain the problem statement and provide a Java solution using dynamic programming.
Problem Statement:
Given a 2D matrix representing a gold mine, we need to find the maximum amount of gold that can be collected by starting at any column of the first row and moving only right, right-up, or right-down in subsequent columns until reaching the last column.
Code Solution:
To solve this problem efficiently, we can use dynamic programming. The idea is to calculate the maximum amount of gold that can be collected at each cell in the matrix by considering the maximum amount of gold that can be collected from the neighboring cells in the previous column. We will iterate column-wise from left to right, updating the values in the matrix.
// Java Program
// Gold Mine Problem
public class GoldMineProblem
{
public void maxGold(int[][] goldMine)
{
int row = goldMine.length;
int col = goldMine[0].length;
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = Integer.MIN_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
System.out.println(max);
}
public static void main(String[] args)
{
GoldMineProblem task = new GoldMineProblem();
int[][] matrix = {
{
14 , 5 , 6 , 9 , 3
},
{
12 , 9 , 7 , 10 , 2
},
{
15 , 6 , 8 , 3 , 1
},
{
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix);
}
}Output
45// Include header file
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
// C++ Program
// Gold Mine Problem
class GoldMineProblem
{
public: void maxGold(vector < vector < int >> goldMine)
{
int row = goldMine.size();
int col = goldMine[0].size();
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = INT_MIN;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
cout << max << endl;
}
};
int main()
{
GoldMineProblem *task = new GoldMineProblem();
vector < vector < int >> matrix
{
{
14 , 5 , 6 , 9 , 3
} , {
12 , 9 , 7 , 10 , 2
} , {
15 , 6 , 8 , 3 , 1
} , {
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
task->maxGold(matrix);
return 0;
}Output
45// Include namespace system
using System;
// Csharp Program
// Gold Mine Problem
public class GoldMineProblem
{
public void maxGold(int[,] goldMine)
{
int row = goldMine.GetLength(0);
int col = goldMine.GetLength(1);
int max = 0;
for (int i = 1; i < col; ++i)
{
for (int j = 0; j < row; ++j)
{
max = int.MinValue;
if (goldMine[j,i - 1] + goldMine[j,i] > max)
{
// Left
max = goldMine[j,i - 1] + goldMine[j,i];
}
if (j - 1 >= 0 && goldMine[j - 1,i - 1] + goldMine[j,i] > max)
{
// Top Left
max = goldMine[j - 1,i - 1] + goldMine[j,i];
}
if (j + 1 < row && goldMine[j + 1,i - 1] + goldMine[j,i] > max)
{
// Botoom Left
max = goldMine[j + 1,i - 1] + goldMine[j,i];
}
goldMine[j,i] = max;
}
}
// Check result in last column
max = goldMine[0,col - 1];
for (int i = 1; i < row; ++i)
{
if (max < goldMine[i,col - 1])
{
max = goldMine[i,col - 1];
}
}
Console.WriteLine(max);
}
public static void Main(String[] args)
{
GoldMineProblem task = new GoldMineProblem();
int[,] matrix = {
{
14 , 5 , 6 , 9 , 3
},
{
12 , 9 , 7 , 10 , 2
},
{
15 , 6 , 8 , 3 , 1
},
{
13 , 8 , 9 , 4 , 2
}
};
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix);
}
}Output
45package main
import "math"
import "fmt"
// Go Program
// Gold Mine Problem
type GoldMineProblem struct {}
func getGoldMineProblem() * GoldMineProblem {
var me *GoldMineProblem = &GoldMineProblem {}
return me
}
func(this GoldMineProblem) maxGold(goldMine[][] int) {
var row int = len(goldMine)
var col int = len(goldMine[0])
var max int = 0
for i := 1 ; i < col ; i++ {
for j := 0 ; j < row ; j++ {
max = math.MinInt64
if goldMine[j][i - 1] + goldMine[j][i] > max {
// Left
max = goldMine[j][i - 1] + goldMine[j][i]
}
if j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max {
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]
}
if j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max {
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]
}
goldMine[j][i] = max
}
}
// Check result in last column
max = goldMine[0][col - 1]
for i := 1 ; i < row ; i++ {
if max < goldMine[i][col - 1] {
max = goldMine[i][col - 1]
}
}
fmt.Println(max)
}
func main() {
var task * GoldMineProblem = getGoldMineProblem()
var matrix = [][] int {
{ 14 , 5 , 6 , 9 , 3 },
{ 12 , 9 , 7 , 10 , 2 },
{ 15 , 6 , 8 , 3 , 1 },
{ 13 , 8 , 9 , 4 , 2 },
}
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix)
}Output
45<?php
// Php Program
// Gold Mine Problem
class GoldMineProblem
{
public function maxGold($goldMine)
{
$row = count($goldMine);
$col = count($goldMine[0]);
$max = 0;
for ($i = 1; $i < $col; ++$i)
{
for ($j = 0; $j < $row; ++$j)
{
$max = -PHP_INT_MAX;
if ($goldMine[$j][$i - 1] + $goldMine[$j][$i] > $max)
{
// Left
$max = $goldMine[$j][$i - 1] + $goldMine[$j][$i];
}
if ($j - 1 >= 0 && $goldMine[$j - 1][$i - 1] +
$goldMine[$j][$i] > $max)
{
// Top Left
$max = $goldMine[$j - 1][$i - 1] + $goldMine[$j][$i];
}
if ($j + 1 < $row && $goldMine[$j + 1][$i - 1] +
$goldMine[$j][$i] > $max)
{
// Botoom Left
$max = $goldMine[$j + 1][$i - 1] + $goldMine[$j][$i];
}
$goldMine[$j][$i] = $max;
}
}
// Check result in last column
$max = $goldMine[0][$col - 1];
for ($i = 1; $i < $row; ++$i)
{
if ($max < $goldMine[$i][$col - 1])
{
$max = $goldMine[$i][$col - 1];
}
}
echo($max.
"\n");
}
}
function main()
{
$task = new GoldMineProblem();
$matrix = array(
array(14, 5, 6, 9, 3),
array(12, 9, 7, 10, 2),
array(15, 6, 8, 3, 1),
array(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
$task->maxGold($matrix);
}
main();Output
45// Node JS Program
// Gold Mine Problem
class GoldMineProblem
{
maxGold(goldMine)
{
var row = goldMine.length;
var col = goldMine[0].length;
var max = 0;
for (var i = 1; i < col; ++i)
{
for (var j = 0; j < row; ++j)
{
max = -Number.MAX_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] + goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] + goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
}
}
// Check result in last column
max = goldMine[0][col - 1];
for (var i = 1; i < row; ++i)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
}
console.log(max);
}
}
function main()
{
var task = new GoldMineProblem();
var matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
];
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix);
}
main();Output
45import sys
# Python 3 Program
# Gold Mine Problem
class GoldMineProblem :
def maxGold(self, goldMine) :
row = len(goldMine)
col = len(goldMine[0])
max = 0
i = 1
while (i < col) :
j = 0
while (j < row) :
max = -sys.maxsize
if (goldMine[j][i - 1] + goldMine[j][i] > max) :
# Left
max = goldMine[j][i - 1] + goldMine[j][i]
if (j - 1 >= 0 and goldMine[j - 1][i - 1] +
goldMine[j][i] > max) :
# Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]
if (j + 1 < row and goldMine[j + 1][i - 1] +
goldMine[j][i] > max) :
# Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]
goldMine[j][i] = max
j += 1
i += 1
# Check result in last column
max = goldMine[0][col - 1]
i = 1
while (i < row) :
if (max < goldMine[i][col - 1]) :
max = goldMine[i][col - 1]
i += 1
print(max)
def main() :
task = GoldMineProblem()
matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
]
# [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix)
if __name__ == "__main__": main()Output
45# Ruby Program
# Gold Mine Problem
class GoldMineProblem
def maxGold(goldMine)
row = goldMine.length
col = goldMine[0].length
max = 0
i = 1
while (i < col)
j = 0
while (j < row)
max = -(2 ** (0. size * 8 - 2))
if (goldMine[j][i - 1] + goldMine[j][i] > max)
# Left
max = goldMine[j][i - 1] + goldMine[j][i]
end
if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
# Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i]
end
if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
# Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i]
end
goldMine[j][i] = max
j += 1
end
i += 1
end
# Check result in last column
max = goldMine[0][col - 1]
i = 1
while (i < row)
if (max < goldMine[i][col - 1])
max = goldMine[i][col - 1]
end
i += 1
end
print(max, "\n")
end
end
def main()
task = GoldMineProblem.new()
matrix = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
]
# [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix)
end
main()Output
45
// Scala Program
// Gold Mine Problem
class GoldMineProblem()
{
def maxGold(goldMine: Array[Array[Int]]): Unit = {
var row: Int = goldMine.length;
var col: Int = goldMine(0).length;
var max: Int = 0;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.MinValue;
if (goldMine(j)(i - 1) + goldMine(j)(i) > max)
{
// Left
max = goldMine(j)(i - 1) + goldMine(j)(i);
}
if (j - 1 >= 0 && goldMine(j - 1)(i - 1) +
goldMine(j)(i) > max)
{
// Top Left
max = goldMine(j - 1)(i - 1) + goldMine(j)(i);
}
if (j + 1 < row && goldMine(j + 1)(i - 1) +
goldMine(j)(i) > max)
{
// Botoom Left
max = goldMine(j + 1)(i - 1) + goldMine(j)(i);
}
goldMine(j)(i) = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine(0)(col - 1);
i = 1;
while (i < row)
{
if (max < goldMine(i)(col - 1))
{
max = goldMine(i)(col - 1);
}
i += 1;
}
println(max);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: GoldMineProblem = new GoldMineProblem();
var matrix: Array[Array[Int]] = Array(
Array(14, 5, 6, 9, 3),
Array(12, 9, 7, 10, 2),
Array(15, 6, 8, 3, 1),
Array(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix);
}
}Output
45import Foundation;
// Swift 4 Program
// Gold Mine Problem
class GoldMineProblem
{
func maxGold(_ goldMine: inout[[Int]])
{
let row: Int = goldMine.count;
let col: Int = goldMine[0].count;
var max: Int = 0;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.min;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine[0][col - 1];
i = 1;
while (i < row)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
i += 1;
}
print(max);
}
}
func main()
{
let task: GoldMineProblem = GoldMineProblem();
var matrix: [[Int]] = [
[14, 5, 6, 9, 3],
[12, 9, 7, 10, 2],
[15, 6, 8, 3, 1],
[13, 8, 9, 4, 2]
];
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(&matrix);
}
main();Output
45// Kotlin Program
// Gold Mine Problem
class GoldMineProblem
{
fun maxGold(goldMine: Array < Array < Int >> ): Unit
{
val row: Int = goldMine.count();
val col: Int = goldMine[0].count();
var max: Int;
var i: Int = 1;
while (i < col)
{
var j: Int = 0;
while (j < row)
{
max = Int.MIN_VALUE;
if (goldMine[j][i - 1] + goldMine[j][i] > max)
{
// Left
max = goldMine[j][i - 1] + goldMine[j][i];
}
if (j - 1 >= 0 && goldMine[j - 1][i - 1] +
goldMine[j][i] > max)
{
// Top Left
max = goldMine[j - 1][i - 1] + goldMine[j][i];
}
if (j + 1 < row && goldMine[j + 1][i - 1] +
goldMine[j][i] > max)
{
// Botoom Left
max = goldMine[j + 1][i - 1] + goldMine[j][i];
}
goldMine[j][i] = max;
j += 1;
}
i += 1;
}
// Check result in last column
max = goldMine[0][col - 1];
i = 1;
while (i < row)
{
if (max < goldMine[i][col - 1])
{
max = goldMine[i][col - 1];
}
i += 1;
}
println(max);
}
}
fun main(args: Array < String > ): Unit
{
val task: GoldMineProblem = GoldMineProblem();
val matrix: Array < Array < Int >> = arrayOf(
arrayOf(14, 5, 6, 9, 3),
arrayOf(12, 9, 7, 10, 2),
arrayOf(15, 6, 8, 3, 1),
arrayOf(13, 8, 9, 4, 2)
);
// [15 + 9 + 8 + 10 + 3] = 45
task.maxGold(matrix);
}Output
45Explanation:
We start by defining the
maxGoldmethod that takes a 2D arraygoldMineas input. This method will calculate and output the maximum amount of gold that can be collected.We retrieve the number of rows and columns in the
goldMinematrix usinggoldMine.lengthandgoldMine[0].length, respectively.We initialize a variable
maxto store the maximum amount of gold.We iterate column-wise from the second column (index
1) to the last column. Inside this loop, we iterate row-wise.For each cell, we initialize
maxtoInteger.MIN_VALUE, which is the smallest possible integer value. This ensures that any gold amount will be greater than the initial value ofmax.We consider three possible paths to reach the current cell: from the left, top-left, or bottom-left cell.
We compare the sum of the gold amount in the previous column's cell and the current cell with the current maximum (
max). If it is greater, we updatemaxaccordingly.Similarly, we check the top-left and bottom-left cells if they exist and update
maxif the sum of their gold amounts and the current cell's gold amount is greater.Once we have determined the maximum amount of gold that can be collected at the current cell, we update the value of that cell in the
goldMinematrix.After completing the column-wise iteration, we need to find the maximum value in the last column. We initialize
maxwith the value of the first cell in the last column.We iterate over the remaining cells in the last column and update
maxif a larger value is found.Finally, we output the value of
max, which represents the maximum amount of gold that can be collected.
Example Output:
In the given example, the maximum amount of gold that can be collected is 45. The path that yields this maximum value is [15, 9, 8, 10, 3].
The Gold Mine Problem can be efficiently solved using dynamic programming techniques. By breaking down the problem into subproblems and calculating the maximum amount of gold at each cell, we can find the overall maximum amount of gold that can be collected. The Java implementation provided in this article demonstrates the step-by-step process of solving the problem. By understanding the problem statement and the corresponding solution, you can apply similar techniques to solve other dynamic programming problems efficiently.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment