Алгоритм балансировки для выравнивания различий?

Question

Скажите, у нас есть N количество счетов с положительными остатками B_1, ..., B_n.

Мы можем сделать перевод T(from,to,amount), который перемещает определенную сумму баланса между счетами.

У нас есть знания об оптимальном распределении остатков O_1, ..., O_n.

Вопрос: Как мы можем найти минимальный набор передач, которые достигают оптимального распределения? Можем ли мы всегда уйти с N-1 переводами в лучшем случае?

Пример:

Balances {0}: 10, {1}: 40, {2}: 50 
Optimal {0}: 20, {1}: 60, {2}: 20 

T(2,0,10) => {0}: 20, {1}: 40, {2}: 40 
T(2,1,20) => {0}: 20, {1}: 60, {2}: 20 

Answer 1

Да, вы всегда можете уйти с не более N-1 передачи. Вот доказательство по индукции:

1. Для N=2 очевидно, что требуется не более одной передачи.
2. Для N>2, есть два случая:
   1. Мы уже при оптимальном распределении, в этом случае нет ничего сделать.
   2. Существует i и j такие, что B_i > O_i и B_j < O_j. Перевод min(B_i - O_i, O_j - B_j) со счета i на счет j. Это балансирует один из двух учетных записей, тем самым уменьшая проблему до N-1.

Доказательство является конструктивным, что дает вам алгоритм. Алгоритм не пытается минимизировать количество передач.

Легко придумать эвристику для уменьшения количества шагов. Для меня немного поздно, чтобы я много думал о оптимальности, но меня не удивило бы, если бы проблема оказалась NP-жесткой.