算法设计：金矿问题解析和代码实现

2021年3月11日17:50:44 发表评论 804 次浏览

本文概述

给定一个n * m尺寸的金矿。该矿场中的每个字段都包含一个正整数, 该整数是黄金的吨数。最初, 矿工位于第一列, 但可以位于任何行。他只能从给定单元移动(右->, 右向上/, 右向下\), 矿工可以向右或向右对角向上或向右对角向下向该单元移动。找出他可以收集的最大数量的黄金。

例子：

Input : mat[][] = {{1, 3, 3}, {2, 1, 4}, {0, 6, 4}};
Output : 12 
{(1, 0)->(2, 1)->(2, 2)}

Input: mat[][] = { {1, 3, 1, 5}, {2, 2, 4, 1}, {5, 0, 2, 3}, {0, 6, 1, 2}};
Output : 16
(2, 0) -> (1, 1) -> (1, 2) -> (0, 3) OR
(2, 0) -> (3, 1) -> (2, 2) -> (2, 3)

Input : mat[][] = {{10, 33, 13, 15}, {22, 21, 04, 1}, {5, 0, 2, 3}, {0, 6, 14, 2}};
Output : 83

资源Flipkart采访

推荐：请在"实践首先, 在继续解决方案之前。

创建与给定矩阵mat [] []相同的二维矩阵goldTable [] [])。如果我们仔细观察这个问题, 我们会注意到以下情况。

  1. 黄金数量为正, 因此我们希望在给定约束下覆盖最大值的最大像元。
  2. 在每一步中, 我们都向右侧移动了一步。因此, 我们总是最后一列。如果我们在最后一列, 那么我们将无法向右移动

如果我们在第一行或最后一列, 那么我们将无法向右上移, 因此只需分配0即可, 否则将goldTable [row-1] [col + 1]的值分配给right_up。如果我们在最后一行或最后一列, 那么我们将无法向下移动, 因此只分配0即可, 否则将goldTable [row + 1] [col + 1]的值分配给右侧。

现在找到right, right_up和right_down的最大值, 然后将其与该mat [row] [col]相加。最后, 找到所有行和第一列的最大值并返回它。

C ++

// C++ program to solve Gold Mine problem
#include<bits/stdc++.h>
using namespace std;
  
const int MAX = 100;
  
// Returns maximum amount of gold that can be collected
// when journey started from first column and moves
// allowed are right, right-up and right-down
int getMaxGold( int gold[][MAX], int m, int n)
{
     // Create a table for storing intermediate results
     // and initialize all cells to 0. The first row of
     // goldMineTable gives the maximum gold that the miner
     // can collect when starts that row
     int goldTable[m][n];
     memset (goldTable, 0, sizeof (goldTable));
  
     for ( int col=n-1; col>=0; col--)
     {
         for ( int row=0; row<m; row++)
         {
             // Gold collected on going to the cell on the right(->)
             int right = (col==n-1)? 0: goldTable[row][col+1];
  
             // Gold collected on going to the cell to right up (/)
             int right_up = (row==0 || col==n-1)? 0:
                             goldTable[row-1][col+1];
  
             // Gold collected on going to the cell to right down (\)
             int right_down = (row==m-1 || col==n-1)? 0:
                              goldTable[row+1][col+1];
  
             // Max gold collected from taking either of the
             // above 3 paths
             goldTable[row][col] = gold[row][col] +
                               max(right, max(right_up, right_down));
                                                      
         }
     }
  
     // The max amount of gold collected will be the max
     // value in first column of all rows
     int res = goldTable[0][0];
     for ( int i=1; i<m; i++)
         res = max(res, goldTable[i][0]);
     return res;
}
  
// Driver Code
int main()
{
     int gold[MAX][MAX]= { {1, 3, 1, 5}, {2, 2, 4, 1}, {5, 0, 2, 3}, {0, 6, 1, 2}
     };
     int m = 4, n = 4;
     cout << getMaxGold(gold, m, n);
     return 0;
}

Java

// Java program to solve Gold Mine problem
import java.util.Arrays;
  
class GFG {
      
     static final int MAX = 100 ;
      
     // Returns maximum amount of gold that 
     // can be collected when journey started 
     // from first column and moves allowed 
     // are right, right-up and right-down
     static int getMaxGold( int gold[][], int m, int n)
     {
          
         // Create a table for storing 
         // intermediate results and initialize
         // all cells to 0. The first row of
         // goldMineTable gives the maximum 
         // gold that the miner can collect 
         // when starts that row
         int goldTable[][] = new int [m][n];
          
         for ( int [] rows:goldTable)
             Arrays.fill(rows, 0 );
      
         for ( int col = n- 1 ; col >= 0 ; col--)
         {
             for ( int row = 0 ; row < m; row++)
             {
                  
                 // Gold collected on going to 
                 // the cell on the right(->)
                 int right = (col == n- 1 ) ? 0 
                         : goldTable[row][col+ 1 ];
      
                 // Gold collected on going to 
                 // the cell to right up (/)
                 int right_up = (row == 0 ||
                                col == n- 1 ) ? 0 :
                         goldTable[row- 1 ][col+ 1 ];
      
                 // Gold collected on going to 
                 // the cell to right down (\)
                 int right_down = (row == m- 1 
                             || col == n- 1 ) ? 0 :
                           goldTable[row+ 1 ][col+ 1 ];
      
                 // Max gold collected from taking
                 // either of the above 3 paths
                 goldTable[row][col] = gold[row][col]
                  + Math.max(right, Math.max(right_up, right_down));
                                                         ;
             }
         }
      
         // The max amount of gold collected will be
         // the max value in first column of all rows
         int res = goldTable[ 0 ][ 0 ];
          
         for ( int i = 1 ; i < m; i++)
             res = Math.max(res, goldTable[i][ 0 ]);
              
         return res;
     }
      
     //driver code
     public static void main(String arg[])
     {
         int gold[][]= { { 1 , 3 , 1 , 5 }, { 2 , 2 , 4 , 1 }, { 5 , 0 , 2 , 3 }, { 0 , 6 , 1 , 2 } };
                          
         int m = 4 , n = 4 ;
          
         System.out.print(getMaxGold(gold, m, n));
     }
}
  
// This code is contributed by Anant Agarwal.

Python3

# Python program to solve
# Gold Mine problem
  
MAX = 100
  
# Returns maximum amount of
# gold that can be collected
# when journey started from
# first column and moves
# allowed are right, right-up
# and right-down
def getMaxGold(gold, m, n):
  
     # Create a table for storing
     # intermediate results
     # and initialize all cells to 0.
     # The first row of
     # goldMineTable gives the
     # maximum gold that the miner
     # can collect when starts that row
     goldTable = [[ 0 for i in range (n)]
                         for j in range (m)]
  
     for col in range (n - 1 , - 1 , - 1 ):
         for row in range (m):
  
             # Gold collected on going to
             # the cell on the rigth(->)
             if (col = = n - 1 ):
                 right = 0
             else :
                 right = goldTable[row][col + 1 ]
  
             # Gold collected on going to
             # the cell to right up (/)
             if (row = = 0 or col = = n - 1 ):
                 right_up = 0
             else :
                 right_up = goldTable[row - 1 ][col + 1 ]
  
             # Gold collected on going to
             # the cell to right down (\)
             if (row = = m - 1 or col = = n - 1 ):
                 right_down = 0
             else :
                 right_down = goldTable[row + 1 ][col + 1 ]
  
             # Max gold collected from taking
             # either of the above 3 paths
             goldTable[row][col] = gold[row][col] + max (right, right_up, right_down)
                                                             
     # The max amount of gold
     # collected will be the max
     # value in first column of all rows
     res = goldTable[ 0 ][ 0 ]
     for i in range ( 1 , m):
         res = max (res, goldTable[i][ 0 ])
  
     return res
      
# Driver code
gold = [[ 1 , 3 , 1 , 5 ], [ 2 , 2 , 4 , 1 ], [ 5 , 0 , 2 , 3 ], [ 0 , 6 , 1 , 2 ]]
  
m = 4
n = 4
  
print (getMaxGold(gold, m, n))
  
# This code is contributed
# by Soumen Ghosh.

C#

// C# program to solve Gold Mine problem 
using System; 
  
class GFG 
{ 
     static int MAX = 100; 
  
     // Returns maximum amount of gold that 
     // can be collected when journey started
     // from first column and moves allowed are 
     // right, right-up and right-down 
     static int getMaxGold( int [, ] gold, int m, int n) 
     { 
          
         // Create a table for storing intermediate 
         // results and initialize all cells to 0. 
         // The first row of goldMineTable gives
         // the maximum gold that the miner 
         // can collect when starts that row 
         int [, ] goldTable = new int [m, n]; 
          
         for ( int i = 0; i < m; i++)
             for ( int j = 0; j < n; j++)
                 goldTable[i, j] = 0;
      
         for ( int col = n - 1; col >= 0; col--) 
         { 
             for ( int row = 0; row < m; row++) 
             { 
                 // Gold collected on going to 
                 // the cell on the right(->) 
                 int right = (col == n - 1) ? 0 :
                             goldTable[row, col + 1]; 
      
                 // Gold collected on going to 
                 // the cell to right up (/) 
                 int right_up = (row == 0 || col == n - 1) 
                             ? 0 : goldTable[row-1, col+1]; 
      
                 // Gold collected on going 
                 // to the cell to right down (\) 
                 int right_down = (row == m - 1 || col == n - 1) 
                                 ? 0 : goldTable[row + 1, col + 1]; 
      
                 // Max gold collected from taking 
                 // either of the above 3 paths 
                 goldTable[row, col] = gold[row, col] + 
                                 Math.Max(right, Math.Max(right_up, right_down)); 
             } 
         } 
      
         // The max amount of gold collected will be the max 
         // value in first column of all rows 
         int res = goldTable[0, 0]; 
         for ( int i = 1; i < m; i++) 
             res = Math.Max(res, goldTable[i, 0]); 
         return res; 
     } 
      
     // Driver Code 
     static void Main() 
     { 
         int [, ] gold = new int [, ]{{1, 3, 1, 5}, {2, 2, 4, 1}, {5, 0, 2, 3}, {0, 6, 1, 2} 
                                 }; 
         int m = 4, n = 4; 
         Console.Write(getMaxGold(gold, m, n)); 
     }
}
  
// This code is contributed by DrRoot_

的PHP

<?php
// Php program to solve Gold Mine problem 
  
// Returns maximum amount of gold that 
// can be collected when journey started 
// from first column and moves allowed are 
// right, right-up and right-down 
function getMaxGold( $gold , $m , $n )
{
     $MAX = 100 ;
      
     // Create a table for storing intermediate 
     // results and initialize all cells to 0. 
     // The first row of goldMineTable gives the 
     // maximum gold that the miner can collect 
     // when starts that row 
     $goldTable = array ( array ());
     for ( $i = 0; $i < $m ; $i ++)
         for ( $j = 0; $j < $n ; $j ++)
             $goldTable [ $i ][ $j ] = 0 ;
              
     for ( $col = $n - 1; $col >= 0 ; $col --) 
     {
         for ( $row = 0 ; $row < $m ; $row ++)
         {
  
             // Gold collected on going to 
             // the cell on the rigth(->) 
             if ( $col == $n - 1)
                 $right = 0 ;
             else
                 $right = $goldTable [ $row ][ $col + 1];
  
             // Gold collected on going to 
             // the cell to right up (/) 
             if ( $row == 0 or $col == $n - 1) 
                 $right_up = 0 ;
             else
                 $right_up = $goldTable [ $row - 1][ $col + 1]; 
  
             // Gold collected on going to 
             // the cell to right down (\) 
             if ( $row == $m - 1 or $col == $n - 1)
                 $right_down = 0 ;
             else
                 $right_down = $goldTable [ $row + 1][ $col + 1];
  
             // Max gold collected from taking 
             // either of the above 3 paths 
             $goldTable [ $row ][ $col ] = $gold [ $row ][ $col ] + 
                                  max( $right , $right_up , $right_down ); 
         }
     }
      
     // The max amount of gold collected will be the 
     // max value in first column of all rows 
     $res = $goldTable [0][0] ;
     for ( $i = 0; $i < $m ; $i ++) 
         $res = max( $res , $goldTable [ $i ][0]); 
  
     return $res ;
}
      
// Driver code 
$gold = array ( array (1, 3, 1, 5), array (2, 2, 4, 1), array (5, 0, 2, 3), array (0, 6, 1, 2));
  
$m = 4 ;
$n = 4 ;
  
echo getMaxGold( $gold , $m , $n ) ;
  
// This code is contributed by Ryuga
?>

输出如下：

16

时间复杂度：

O(m * n)

空间复杂度：

O(m * n)

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: