максимальное значение стоимости в двумерном массиве, сумма которого меньше или равна заданному числу - PullRequest
Новая
       19

максимальное значение стоимости в двумерном массиве, сумма которого меньше или равна заданному числу

2 голосов
/ 02 августа 2020

Учитывая 2D-массив и число K.

ПРОБЛЕМА: у нас есть матрица cost[][], и каждая ячейка матрицы представляет собой стоимость прохождения через эту ячейку. мы начинаем с верхнего левого угла (0,0) и должны дойти до последней ячейки (справа внизу). Мне нужно написать функцию, которая возвращает стоимость пути с максимальной стоимостью для достижения (m,n) без превышения числа K.

Общая стоимость пути для достижения (m, n) - это сумма всех затраты на этом пути (включая источник и место назначения), и сумма должна быть меньше или равна K. Мы можем двигаться только вниз, вправо или по диагонали вниз-вправо.

Если мы не можем найти путь, максимальная сумма которого меньше или равна K, мы возвращаем -1, а значение матрицы не может быть отрицательным

Решение: я пробовал много кодов, но ни один из них не дал ожидаемых результатов.

Моим первым решением было преобразовать 2D-массив в простой массив и применить алгоритм ранца , но он не сработал, потому что логически путь не был пройден. ( лог c упражнения исчезли с этой идеей )

Я пробовал также рекурсивную формулу, но она не сработала. Получил ошибку « максимальная глубина рекурсии ». Когда я решил эту проблему рекурсии, мой алгоритм не учел ограничение числа, которое не должно быть превышено.

Мне не нужен код, мне просто нужны некоторые объяснения, чтобы иметь возможность решить проблему (особенно математическая формула). спасибо

Пример: 

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

ответ должен быть 6 :(0,0)->(1,1)->(3,3)

Ответы [ 2 ]

1 голос
/ 02 августа 2020

Если мы думаем об этом как о поиске наименьшей оставшейся неотрицательной величины, когда мы вычитаем стоимость на нашем пути от конца к началу, наивное повторение может быть примерно следующим. Мемоизированная рекурсия иногда лучше подходит, чем итерация по полному измерению k, потому что многие входные данные могут дать идиосинкразию c наборов сумм. 

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));
0 голосов
/ 02 августа 2020

Допустим, dp[i][j] - это стоимость go до локации (i,j), тогда стоимость зависит от стоимости достижения предыдущей локации, из которой будет достигнута текущая локация:

  • по диагонали вниз-вправо (i-1,j-1)
  • или вниз по столбцу (i-1,j)
  • или вправо (i, j-1).

Теперь уравнения можно записать как: 

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] )

Используя их, вы можете построить массив dp снизу вверх, и ваш ответ будет dp[m][n], где m x n - размер двумерного массива.

...