Задача на ДП

[JetB]

Добрый день.

Ещё давно я столкнулся с задачей, которую не могу решить до сих пор, отчего пришёл сюда за помощью.
Для начала поставлю саму задачу. Предыстория, с которой она подаётся, значения не имеет.

Дана матрица $A$ размера $N\times N$, элементами которой являются натуральные числа. Требуется найти такое подмножество $\left\{\alpha_{ij} \right\}_1^k$, что:
а) $\forall \alpha_1=\alpha_{i_1j_1}, \alpha_2=\alpha_{i_2j_2}, j_1 \neq j_2$
б) $\sum_{m=1}^{k}{i_m} = N$
в) $\sum_{m=1}^{k}{\alpha_m} = \max$

Ясно, что множество индексов $i$ является композицией числа $N$. Поэтому первым абстрактным решением является генерация композиций числа $N$, являющихся номерами строк, откуда взяты элементы $\alpha$. Затем последовательно, для каждого слагаемого ищем максимальный элемент в соответствующей стоке, из незадействованного ранее столбца. Но в силу ограничений на $N$ такой брутальный алгоритм не пройдёт, что ежу понятно. Да и динамикой тут не пахнет. Можно задумать о том, что в композициях слагаемые упорядочены, поэтому, для ускорения работы программы можно попробовать рассмотреть всё то же множество индексов $i$ уже как разбиение числа $N$. Но тогда нужно применять какую-то эвристику, чтобы понять, в каком порядке рассматривать строки, в поисках максимального элемента. Но и в этом случае динамики в решении не наблюдается, и оно далеко не оптимально.

Если задуматься о том, что задача отнесена в группу "Динамическое программирование", то можно попытаться "плясать от этого". Но тогда встаёт вопрос "Какую подзадачу выбрать"? Решать сперва подзадачу для матрицы $N \times (N-1)$ не вариант, так как с добавлением столбца мы получаем новую задачу, для решения которой нельзя использовать решение предыдущей подзадачи. Можно сначала рассмотреть матрицу $(N-1) \times N$, но тогда не очевидно как использовать решение подзадачи.

В общем я попал вот в такой тупик. ДП никогда не было моей сильной стороной, так что я вполне мог упустить что-то, или сделать неверный вывод. Если можно - очень хочется получить указание на ошибку в рассуждениях, или намёк на то, в каком направлении капать.

Спасибо!

[nikvic]

Есть ли содержательная трактовка?

[JetB]

Цитата с сайта, откуда взята задача:
"Многие, вероятно, слышали песни про приключения лягушонка Crazy Frog. На этот раз неугомонное милое создание решило подкрепиться, но даже такое простое действие решило выполнить в виде игры. Итак, в каждой клетке квадратного игрового поля, разбитого на $N\times N$ ($N \leq 50$) клеток, находится комар весом $a_{ij}$ (вес комара – натуральное число $\leq 50$), i - номер строки, j - номер столбца. Лягушонок, прыгая с клетки на клетку, ест комаров. Правила игры таковы - в каждом столбце можно съесть не более одного комара. Всякий раз при съедании комара запоминаем номер строки, откуда съеден комар, и сумма номеров строк, в которых были съедены комары, в конце игры должна быть в точности равна $N$. Учтите, если из какой-то строки съедено несколько комаров, то номер данной строки участвует в суммировании более одного раза.

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

[venco]

Отделите все $N$ друг от друга, и получится DP.
Т.е. пусть матрица $M\times N$, а $\sum_{m=1}^{k}{i_m} = S$.
Меняющиеся параметры DP - $M$ и $S$.

[JetB]

venco, да, я указал этот вариант "индукции по строкам". Но сколько не пытался - не могу придумать алгоритм, позволяющий найти решение для матрицы $M\times N$, используя решения для $(M-1)\times N$.

То есть имеется матрица $A'$, размеров $(M-1)\times N$, для которой найдено решение $\left\{\alpha_{ij} \right\}_{1}^k$, и новая строка $1\times N$. Тогда нужно проверить эту строку на наличие таких элементов $x: \exists \left\{\alpha'_{ij} \right\}_1^t \subseteq \left\{\alpha_{ij} \right\}_{1}^k : \sum_{1}^{t}{\alpha'_m} < x, \sum_{1}^{t}{i_m} \geq M$. При этом такой выбор может быть не один. Да и правило о том, что элементы должны быть из разных столбцов, фактически может насильно "вклинить" какой-то элемент в это подмножество $\left\{\alpha'_{ij} \right\}$. Да и не понятно, что делать в случае $\sum_{1}^{t}{i_m} > M$.