Задача оптимизации в таблице

Revision ru1, by always_first, 2016-05-13 22:10:40

Всем привет!

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

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

Tags оптимизация, задача о назначениях

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English always_first 2016-05-14 00:59:43 52
en1 English always_first 2016-05-13 22:53:31 763 Initial revision for English translation
ru1 Russian always_first 2016-05-13 22:10:40 799 Первая редакция (опубликовано)