PHP Lang
  1. PHP Lang
  3. Получите наименьшую сумму комбинации матричных элементов
Intereting Posts
Как проверить, является ли URL-адрес внешним URL-адресом или внутренним URL-адресом с помощью PHP? PHP – Как добавить заголовок страницы в URL? И как создать чистый URL-адрес с помощью PHP преобразование изображения blob в файл в php Symfony2 сериализует объект объекта на сеанс Вызов функции PHP каждую секунду Вопросительный знак равен, не работает на php Как заставить CURL работать с PHP в Windows? (WAMP) Как отключить буферизацию вывода в PHP Подсчет значений значения в столбце массива массивов объектов Является ли это разумным способом обработки getters / seters в классе PHP? Как хранить строку / столбец данных mysql в массиве чтение docx (Office Open XML) в PHP PHP 'file_get_contents' не работает с сервера Перенаправить * .php для очистки URL-адреса cakephp datasource Вызов неопределенного метода

Получите наименьшую сумму комбинации матричных элементов

Вчера один из моих друзей пришел с проблемой, попросив меня найти решение.

Проблема

У меня есть matrix(nxm) . Мне нужно узнать наименьшую сумму, которую я могу произвести из этого матричного элемента.

Условие:

  • Подсчет должен начинаться только с верхней левой ячейки. А также
  • Должен заканчиваться в нижней правой ячейке.
  • Алгоритм должен учитывать все возможные пути
  • Таким образом, мне нужно найти возможную наименьшую сумму.

После нескольких часов работы я смогу найти образец для этого. Но я не знаю, как реализовать его в коде.

Вот мой пример:

введите описание изображения здесь

Как я могу это реализовать?

Редактировать : 

 $Cost = array(); for ($x = 0; $x < $rows; $x++) { $Cost[0][$x] = $matrix[0][$x]; for ($y = 1; $y < $cols; $y++) { $Cost[$y][0] = $matrix[$y][0]; } } for ($x = 1; $x < $rows; $x++) { for ($y = 1; $y < $cols; $y++) { $Cost[$x][$y] = intval($matrix[$x][$y]) + min(intval($Cost[$x - 1][$y]), intval($Cost[$x][$y - 1])); } }

Матричный массив Я пытаюсь: 

 array(2) { [0]=> array(3) { [0]=> string(1) "3" [1]=> string(2) "44" [2]=> string(2) "75" } [1]=> array(3) { [0]=> string(2) "21" [1]=> string(2) "98" [2]=> string(2) "60" } }

Результат: 

 array(3) { [0]=> array(2) { [0]=> string(1) "3" [1]=> string(2) "44" } [1]=> array(3) { [0]=> string(2) "21" [1]=> int(119) [2]=> int(0) } [2]=> array(1) { [0]=> NULL } }

Solutions Collecting From Web of "Получите наименьшую сумму комбинации матричных элементов"

Кажется, что вы можете идти только вправо и вниз. Для этого случая (в противном случае используйте алгоритмы поиска пути) обратите внимание, что вы можете войти в каждую ячейку либо из верхней ячейки, либо из левой ячейки. Самый дешевый путь к этой ячейке будет минимальным из этих значений. Таким образом, решение DP может выглядеть как (псевдокод):

см. исправления здесь 

 Cost[0, 0] = matrix[0, 0] for x = 1 to cols - 1 Cost[0, x] = matrix[0, x] + Cost[0, x-1] //0th row for y = 1 to rows - 1 Cost[y, 0] = matrix[y, 0] + Cost[y-1, 0] //0th column //proper filling of 0th row and 0th column for y = 1 to rows - 1 for x = 1 to cols - 1 Cost[y, x] = matrix[y, x] + Min(Cost[y-1, x], Cost[y, x-1])

то стоимость [n-1, n-1] – это то, что вам нужно

Обновление для ответа MBo . Учитывая * m (n = 3, m = 4 в вашем сообщении) Расходуемое пространство можно уменьшить до O (N), только запомнив результат для предыдущей строки (столбца). 

 Cost[0] = matrix[0, 0] for x = 1 to m - 1 Cost[x] = matrix[0, x] + Cost[x-1] for y = 1 to n - 1 Cost[0] += matrix[y, 0] for x = 1 to m - 1 Cost[x] = matrix[y, x] + Min(Cost[x-1], Cost[x]) output(Cost[n-1])

Не знаю, как писать на PHP … Вот пример кода python 

 matrix = [ [3, 44, 75], [21, 98, 60], ] n = len(matrix) m = len(matrix[0]) cost = [0] * m cost[0] = matrix[0][0] for x in xrange(1, m): cost[x] = matrix[0][x] + cost[x-1] for y in xrange(1, n): cost[0] += matrix[y][0] for x in xrange(1, m): cost[x] = matrix[y][x] + min(cost[x-1], cost[x]) print cost[-1]