Всем привет!
Недавно я ознакомился с венгерским алгоритмом решения задачи о назначениях. Мне стало любопытно, можно ли за полиномиальное время решить более общий случай: в таблице n × m выбрать числа таким образом, что сумма выбранных чисел была максимальна, причем в каждой строке были выбраны не менее Rmin и не более Rmax чисел, а в каждом столбце были выбраны не менее Cmin и не более Cmax чисел.
При Rmin = Rmax = 1 и Cmin = Cmax = 1 это задача о назначениях. А что можно сказать о более общем случае? Есть ли у вас какие-то мысли по этому поводу (может быть, хотя бы в более частном случае Rmin = Rmax = R и Cmin = Cmax = C)? Буду благодарен любым идеям.
