maximum cost value in a 2D array having sum less or equal than a given number

user_14036620 0
Viewed 214

Given a 2D-array and a number K.

PROBLEM: we have a matrix cost[][] and each cell of the matrix represents a cost to traverse through that cell. we start at the top left (0,0) and we have to reach the last cell (bottom right). I have to write a function that returns the cost of maximum cost path to reach (m,n) without exceeding the number K.

The total cost of a path to reach (m, n) is the sum of all the costs on that path (including both source and destination) and the sum should be less or equal than K. We can only move down, right or diagonally down-right.

If we can't find a path having a maximum sum less or equal than K we return -1 and the value of the matrix cannot be negative

Solution: I tried a lot of codes but none of them returned the results I expected.

My first solution was to transform the 2D array in a simple array and to apply the knapsack algorithm but it didn't work because logically the path were not followed. (the logic of the exercise disappeared with this idea)

I tried also a recursive formula but it didn't work. I got an error "max recursion depth". When I solved this recursion problem my algorithm didn't take into account the constraint of the number not to be exceeded.

I don't need the code, I just want some explanations to be able to solve the problem (especially the mathematical formula). thanks

Example:

    if we had this 3*3 matrix:
    cost[][] = {{2,3,1}, {6,1,9},{8,2,3}}
    and k = 7

the answer should be 6 :(0,0)->(1,1)->(3,3)

dynamic-programming matrix algorithm python
2 Answers

If we think about it as searching for the smallest remaining non-negative magnitude as we subtract the cost on our way from the end to the start, a naive recurrence could be something like the following. A memoised recursion is sometimes better suited than an iteration on the full dimension of k because many inputs can yield idiosyncratic sets of sums.

function g(m, K, i, j, k, memo){
  if (k < 0 || i < 0 || j < 0)
    return K + 1;

  if (i == 0 && j == 0)
    return k >= m[i][j] ? k - m[i][j] : K + 1;
    
  const key = String([i, j, k]);
  
  if (memo.hasOwnProperty(key))
    return memo[key];
    
  return memo[key] = Math.min(
    g(m, K, i-1, j, k - m[i][j], memo),
    g(m, K, i, j-1, k - m[i][j], memo),
    g(m, K, i-1, j-1, k - m[i][j], memo)
  )
}

function f(m, k){
  return k - g(m, k, m.length-1, m[0].length-1, k, {});
}

var m = [
  [2,3,1],
  [6,1,9],
  [8,2,3]
];

var k = 7;

console.log(f(m, k));

user_20347870

Lets say dp[i][j] is the cost to go to the location (i,j), then the cost depends on the cost to reach its previous location from where the current location be reached :

  • diagonally down-right (i-1,j-1)
  • or down a column (i-1,j)
  • or right (i, j-1).

Now the equations can be written as:

dp[i][j] = -1
if ( cost[i][j] < K ):
    dp[i][j] = if ( dp[i-1][j-1] != -1 and cost[i][j] + dp[i-1][j-1] <= K ) :
                  dp[i][j] = cost[i][j] + dp[i-1][j-1]

               if ( dp[i-1][j] != -1 and cost[i][j] + dp[i-1][j] <= K ) :
                  dp[i][j] = max( dp[i][j], cost[i][j] + dp[i-1][j] )

               if ( dp[i][j-1] != -1 and cost[i][j-1] + dp[i][j-1] <= K):
                  dp[i][j] = max( dp[i][j], cost[i][j] + dp[i][j-1] )

Using these you can build a bottom up dp array and your answer will be dp[m][n] where m x n is the size of the 2-d array.

user_14103030
Related