У меня есть таблица значений 5x5 от 0 до 3 включительно со всеми неизвестными значениями. Я знаю как сумму значений, так и количество нулей для каждой строки и столбца. Как я могу решить эту задачу с рюкзаком 0-1 с помощью C # и получить возможные решения, которые удовлетворяют известным суммам и количеству нулей? В таблицах всегда будет пять строк и пять столбцов, так что это не совсем традиционный рюкзак.
Например, скажем, мы вводим:
Row[0]: Sum=4, Zeros=1
[1]: Sum=5, Zeros=1
[2]: Sum=4, Zeros=2
[3]: Sum=8, Zeros=0
[4]: Sum=3, Zeros=2
Col[0]: Sum=5, Zeros=1
[1]: Sum=3, Zeros=2
[2]: Sum=4, Zeros=2
[3]: Sum=5, Zeros=1
[4]: Sum=7, Zeros=0
Мы бы получили это как возможное решение:
[[ 0 1 1 1 1 ]
[ 1 0 2 1 1 ]
[ 2 1 0 0 1 ]
[ 1 1 1 2 3 ]
[ 1 0 0 1 1 ]]
Какой алгоритм мне следует использовать в этой довольно странной ситуации? Придется ли мне также написать класс только для перечисления перестановок?
Отредактируйте для пояснения: проблема не в том, что я не могу перечислить возможности; Дело в том, что я понятия не имею, как эффективно определять перестановки, добавляемые к произвольной сумме, при этом они содержат указанное количество нулей и максимум 5 элементов.