Daniyar91
BANNED | Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
..., и еще очень много умных слов, я слышал.
А если серьезно то все гораздо проще.
расмотрим такую таблицу:
1: 8 2 1 2 3
2: 1 2 6 2 4
3: 2 7 2 3 4
4: 1 3 2 4 4
5: 1 3 4 3 1
наша задача, выявить в каждом столбще самую "ценную" ячейку, потому как в каждом столбце, мы можем взять только одно значение. Ясно что в первом столбще, такая ячейка находится в первой строке (8 -- имеет самое большее значение из всех строк, и стоит один ход), также ясно что пятое значение (1) менее ценно четвертого (1), ведь их значения одинаковы, а стоят они разное кол-во ходов. Также видно что четвертая ячейка менее ценна второй.
из этого делаем вывод, что возможно можно как-то расчитать стоимость кажной ячейки в столбце.
расмотрим такую таблицу:
1 1 1
2 2 2
3 3 3
какие бы ячейки мы не взяли, так и так, мы не наберем в сумме число отличное от 3. делаем вывод, что ценность ячейки прямопропорцеонально ее значению, и обратнопропорцеонально индексу строки (стоимости ходов за нее).
возвращаемся к первой тблице и расчитываем ценность каждой ячейки
1: 8-1= 7 2-1= 1 1-1= 0 2-1= 1 3-1= 2
2: 1-2=-1 2-2= 0 6-2= 4 2-2= 0 4-2= 2
3: 2-3=-1 7-3= 4 2-3=-1 3-3= 0 4-3= 1
4: 1-4=-3 3-4=-1 2-4=-2 4-4= 0 4-4= 0
5: 1-5=-4 3-5=-2 4-5=-1 3-5=-2 1-5=-4
т.е. получилось вот так:
1: 7 1 0 1 2
2: -1 0 4 0 2
3: -1 4 -1 0 1
4: -3 -1 -2 0 0
5: -4 -2 -1 -2 -4
теперь берем самые ценные ячеки -- 7(1:1), потратили один ход, значит осталось еще четыре хода. видим что следующая по цене это ячейка 4(2:3) и 4(3:2), естетсвеноо берем ту за которую тратим меньше ходов - (3:2), потратили еще два хода, осталось еще два. следующая ячейка это та которую мы не взяли на предыдущем ходе 4(2:3), но на нее надо 3 хода, а у нас всего 2, а значит мы не должны искать в тех строках куда нехватает ходов, а значит теперь смотрим только на две первые строки, и видим ячейки 2(5:1) и 2(5:2) понятно что берем (5:1), остался один ход, значит смотрим только в первой строке, а это либо 1(2:1) либо 1(4:1), возьмем допустим 1(2:1). все, ходы кончились, мы выбрали следующие ячейки: (1:1), (3:2), (5:1), (2:1), смотрим в первую таблицу, и по-этим тндексам находятся следующие значения 8, 6, 3, 2. в сумме 19.
P.S. я до этого долго шел. т.е. тоже всякие там рекурсии хотел использовать, но до написания кода, дело так и не дошло, потому-что времени свободного очень мало.
P.P.S. Возможно это не работает, нодо проверять, но мне лень. |
Всего записей: 425 | Зарегистр. 30-08-2011 | Отправлено: 13:35 19-09-2015 | Исправлено: Daniyar91, 18:25 19-09-2015 |
|
