Всем привет!

Недавно я ознакомился с венгерским алгоритмом решения задачи о назначениях. Мне стало любопытно, можно ли за полиномиальное время решить более общий случай: в таблице n × m выбрать числа таким образом, что сумма выбранных чисел была максимальна, причем в каждой строке были выбраны не менее R_min и не более R_max чисел, а в каждом столбце были выбраны не менее C_min и не более C_max чисел.

При R_min = R_max = 1 и C_min = C_max = 1 это задача о назначениях. А что можно сказать о более общем случае? Есть ли у вас какие-то мысли по этому поводу (может быть, хотя бы в более частном случае R_min = R_max = R и C_min = C_max = C)? Буду благодарен любым идеям.