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

Question

У меня есть счета с положительным и отрицательным балансом и отношения залога между некоторыми. Залог дает счетам с отрицательным балансом право на получение денег с залогового счета для покрытия их потери.

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

            1    2    3
A 1000 | -1000 -500 -500
B 1000 | -1000

В данном примере счета A и B имеют положительное сальдо 1000, а счета 1,2,3 имеют приоритет (1> 2> 3). Я хочу покрыть как можно больше счетов, распределив деньги А и Б на 1,2,3, соблюдая при этом приоритет.

В этом конкретном примере выбор A1 в качестве моей первой пары приведет к покрытию только 1000, но если я выберу B1, A2, A3, у меня будет оптимальное решение для покрытия 2000.

Как называется такая проблема оптимизации и каковы алгоритмы ее решения?

Answer 1

Это в основном проблема сетевого потока. Я нарисую емкостный график для вашего примера (немаркированные дуги имеют бесконечную емкость). s является источником, а t является приемником.

     >A------->1
1000/ |\       ^\
   /  | \     /  \1000
  /   |  \   /    \
 /    |   \ /  500 v
s     |    /->2--->t
 \     \  /        ^
  \     \/        /
   \    /\       /500
1000\  /  \     /
     >B    --->3

Ответ не максимальный поток; это поток, который максимизирует 1, затем 2, затем 3. Один многочастичный алгоритм состоит в том, чтобы модифицировать алгоритм максимального потока на основе увеличения путей (простых путей! - в противном случае мы могли бы убрать поток из учетной записи с более высоким приоритетом) преимущественно для увеличения путей через 1, затем 2, затем 3.

Answer 2

Моя ассоциация говорит, что вы можете найти информацию в этой области, если «Проблемы с упаковкой» (применяются вне области геометрии)

Будучи не экспертом в этой области, я нашел следующие темы, которые кажутся актуальными:*

• http://en.wikipedia.org/wiki/Bin_packing_problem
• http://en.wikipedia.org/wiki/Cutting_stock_problem
• http://en.wikipedia.org/wiki/Subset_sum_problem

возможно даже связанных:

• http://en.wikipedia.org/wiki/Fragmentation_(computer)