|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
28.01.2016, 16:24 | #1 |
Регистрация: 28.01.2016
Сообщений: 3
|
самый дешевый путь
В каждой клетке прямоугольной таблицы NM записано некоторое число. Изначально игрок находится в левой верхней клетке. За один ход ему разрешается перемещаться в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). При проходе через клетку с игрока берут столько килограммов еды, какое число записано в этой клетке (еду берут также за первую и последнюю клетки его пути).
Требуется найти минимальный вес еды в килограммах, отдав которую игрок может попасть в правый нижний угол. Входные данные Вводятся два числа N и M — размеры таблицы (1N20, 1M20). Затем идет N строк по M чисел в каждой — размеры штрафов в килограммах за прохождение через соответствующие клетки (числа от 0 до 100). Выходные данные Выведите минимальный вес еды в килограммах, отдав которую можно попасть в правый нижний угол. Примеры входные данные 5 5 1 1 1 1 1 3 100 100 100 100 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 выходные данные 11 При чем здесь PHP? Перемещаю в помощь студентам И укажи на каком языке Последний раз редактировалось Аватар; 28.01.2016 в 16:29. |
28.01.2016, 17:00 | #2 |
Старожил
Регистрация: 15.02.2010
Сообщений: 15,758
|
О! Можно бектрекингом побаловаться...
|
28.01.2016, 17:13 | #3 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Или подобием алгоритма Дейкстры.
|
28.01.2016, 17:19 | #4 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
погуглите "динамическое программирование черепашка"
Единственное отличие, что в классической задаче идёт поиск максимума, а в данной - поиск минимума. |
28.01.2016, 17:34 | #5 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Наверное, нужно сначала подсчитать цену перемещения строго вправо и строго вниз. А потом перейти к клетке [2,2] и из неё двигаться вправо и вниз, выбирая самую дешёвую цену из двух возможных. И так до самой последней клетки.
|
28.01.2016, 18:37 | #6 | |
Вредный кошак
Участник клуба
Регистрация: 14.10.2012
Сообщений: 1,159
|
Здесь обычным волновым алгоритмом можно решить без проблем
Цитата:
|
|
28.01.2016, 19:24 | #7 | ||
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Цитата:
Цитата:
А волновой здесь неприменим. |
||
28.01.2016, 21:41 | #8 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
FPaul, ваш алгоритм работать не будет. исходный пример дан уже с этим "подвохом" - из угла два вариант - пойти вниз, стоимость 3 или пойти вправо, стоимость 1
Ваш алгоритм какой путь выберет?! Ну и не понимаю, о чёт тут спорить. Эта задача быстро и просто решается через ДП. Она КЛАССИЧЕСКАЯ азбучная задача для ДП. Вы хотите изобрести велосипед? А зачем? ДП - это динамическое программирование Последний раз редактировалось Вадим Мошев; 28.01.2016 в 21:46. |
28.01.2016, 21:49 | #9 | ||
Вредный кошак
Участник клуба
Регистрация: 14.10.2012
Сообщений: 1,159
|
Цитата:
Вот пример: 0 0 0 0 0 1 1 1 1 10 1 1 1 1 0 если по Вашему алгоритму идти, то получим цену 10, а по другому пути - 2. Цитата:
Фактически, алгоритм Дейкстра. |
||
28.01.2016, 22:33 | #10 | ||
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Цитата:
1-й проход от [1,1] вправо и вниз. В клетки матрицы записываем минимальную сумму Код:
Код:
Код:
Цитата:
Последний раз редактировалось FPaul; 28.01.2016 в 22:38. |
||
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Самый дешевый путь. Графы. | jocry | Помощь студентам | 1 | 14.03.2009 12:56 |