Алгоритм поиска минимального из списка пар

Question

Проблема заявление:

Учитывая список пар {A | B}
Найти минимальную сумму, где вы должны принимать значения «M» с «A» и «п» значения из «B»

• вы не можете использовать один и тот же «пару» для а и в
• размер списка будет находиться в диапазоне от 2 до 500 пунктов
• количествопредметы, которые вы берете (m & n) также могут быть изменены
• цифры в паре (A & B) находятся в диапазоне 0-9.

Конечно, могут быть несколько комбинаций пар, которые дают вам правильный минимум.

Например, учитывая:

1 - {4,5} 
2 - {3,2} 
3 - {3,1} 
4 - {1,0} 

и желая 2 из А, 1 из B
правильный ответ
принимая 2A (3), 4А (1) и 3В (1).

Другой пример:

1 - {5,4} 
2 - {2,1} 
3 - {6,6} 
4 - {2,1} 
5 - {5,5} 

и желая 2 из А, 2 из В
правильный ответ
принимая 1А (5), 5А (5), 2В (1), 4В (1).

Я решил это с использованием подхода грубой силы, но, разумеется, при увеличении списка и увеличении m/n производительность сильно пострадает.

Как я могу улучшить этот подход грубой силы? Что называется этим классом проблем?

Верьте или нет, это не домашнее задание!

Answer 1

Его можно сформулировать как minimum-cost flow problem. Пусть пары будут (a_i, b_i). Создайте вершины s, t, a, b, u_i и дуги от s до a (емкость m, стоимость 0), от s до b (емкость n, стоимость 0), от a до u_i (емкость 1, стоимость a_i), из b до u_i (емкость 1, стоимость b_i), от u_i до t (емкость 1, стоимость 0). Отправьте m + n единиц расхода как можно дешевле с s на t. Поток на a-> u_i означает, что выбрано a_i. Поток на b-> u_i означает, что выбрано b_i.

Он также может быть решен путем динамического программирования. Пусть Cost[i, j, k] - минимальная сумма для выбора i A и j B от первых k пар. Затем мы имеем рекуррентные соотношения.

Cost[0, 0, 0] = 0 
Cost[i, j, 0] = infinity 
    (for all i, j such that i > 0 or j > 0) 
Cost[i, j, k] = min {Cost[i, j, k-1], 
        Cost[i-1, j, k-1] + a_k, 
        Cost[i, j-1, k-1] + b_k} 
    (for all i, j, k such that k > 0). 

Отслеживание минимальных аргументов для восстановления оптимального выбора.