Задача про приключения лягушонка Crazy Frog

Алгоритмы: от сортировки пузырьком до численных методов

Модераторы: C_O_D_E, DeeJayC

Ответить
olya1994
Сообщения: 10
Зарегистрирован: 13 ноя 2014, 23:27

17 сен 2015, 17:41

Всем привет! Помогите пожалуйста решить хитрую задачку! у самой ничего не получается..Заранее огромное Вам спасибо!!! Задача решается через вектора..

Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на N*N (N<=50) клеток, находится один комар весом aij (вес комара – натуральное число <= 50), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна N. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

Определите максимальный вес комаров, который можно съесть при следовании приведённым правилам.

Входные данные

Первая строка входного файла INPUT.TXT содержит число N. Следующие N строк содержат по N чисел aij, разделенных пробелами.

Выходные данные

В выходной файл OUTPUT.TXT выведите целое число – вес съеденных комаров.

Примеры

INPUT.TXT OUTPUT.TXT
3
8 2 1
1 2 6
2 7 2 14
5
8 2 1 2 3
1 2 6 2 4
2 7 2 3 4
1 3 2 4 4
1 3 4 3 1 19
Аватара пользователя
Romeo
Сообщения: 3091
Зарегистрирован: 02 мар 2004, 17:25
Откуда: Крым, Севастополь
Контактная информация:

17 сен 2015, 18:32

Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.
Entites should not be multiplied beyond necessity @ William Occam
---
Для выделения С++ кода используйте конструкцию [ code=cpp ] Код [ /code ] (без пробелов)
---
Сообщение "Спасибо" малоинформативно. Благодарность правильнее высказать, воспользовавшись кнопкой "Reputation" в виде звёздочки, расположенной в левом нижнем углу рамки сообщения.
olya1994
Сообщения: 10
Зарегистрирован: 13 ноя 2014, 23:27

17 сен 2015, 19:57

Romeo писал(а):Перенёс в алгоритмы, так как задача привязана не столько к языку, сколько необходимо нахождение изящного алгоритма, который будет более быстр, чем полный перебор. Мне с первого взгляда кроме полного перебора ничего в голову не приходит. Попробую позже подумать над задачей, может осенит.
Огромное спасибо Вам! Я думаю возможно такой алгоритм!?
1 цикл - перебираем столбцы исходной матрицы
2 цикл - перебираем массив сумм
3 цикл - перебираем столбец исходной матрицы (для каждого значения в массиве сумм ищем в столбце лучший вариант)
Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

18 сен 2015, 21:56

Очевидно комары будут съедаться в основном из верхних строк, т.к. чем меньше номер строки, тем большее число клеток мы сможем охватить. Наверное было бы неплохо предварительно значения в матрице с весом комаров построчно поделить на номер строки, тем самым узнав реально эффективный вес. А дальше строим допустимые маршруты и считаем суммы. Имхо только перебором, т.к. комбинаторика на лицо.
It's a long way to the top if you wanna rock'n'roll
Ответить