Задача оптимизации в таблицеOptimization problem in table
Разница между ru1 и en1, 763 символ(ов) изменены
Всем привет!↵

Недавно я ознакомился с [венгерским алгоритмом](http://e-maxx.ru/algo/assignment_hungary) решения задачи о назначениях. Мне стало любопытно, можно ли за полиномиальное время решить более общий случай: в таблице $n \times m$ выбрать числа таким образом, что сумма выбранных чисел была максимальна, причем в каждой строке были выбраны не менее $R_{min}$ и не более $R_{max}$ чисел, а в каждом столбце были выбраны не менее $C_{min}$ и не более
Hi everybody!↵

Recently I've learned hungarian algorithm for solving the assignment problem, Now I'm curious about how to solve more common problem: for given $n \times m$ table select several numbers, maximizing their sum with following constraints: in each row the number of selected numbers is not less than $R_{min}$ and not more than $R_{max}$, and for each column the number of selected numbers is not less than $C_{min}$ and not more than
 $C_{max}$ чисел. .

ПриIf $R_{min} = R_{max} = 1$ иand $C_{min} = C_{max} = 1$ это задача о назначениях. А что можно сказать о более общем случае? Есть ли у вас какие-то мысли по этому поводу (может быть, хотя бы в более частном случаеthis is the standard assignment problem. But what can we say about more common case? Any thoughts about this (maybe, at least in case $R_{min} = R_{max} = R$ и, $C_{min} = C_{max} = C$)? Буду благодарен любым идеямAny ideas would be appreciated

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский always_first 2016-05-14 00:59:43 52
en1 Английский always_first 2016-05-13 22:53:31 763 Initial revision for English translation
ru1 Русский always_first 2016-05-13 22:10:40 799 Первая редакция (опубликовано)