Алгоритм подсчета сумм доплат

Нужен совет пользователей сервиса как считать суммы доплат. Имеются такие варианты:

Если денег предлагается больше чем требуется. Объявление, от которого строим цепочку, желает получить доплату.

Способ №1. Показываем максимум, который может получить объявление для которого построена цепочка

Для того чтобы посчитать максимальную сумму, которую может получить объявление для которого построена цепочка, мы должны сложить все суммы, которые отдаются в цепочке и вычесть из них все суммы, которые требуются в цепочке. К остатку прибавляем заявленную в объявлении сумму требующейся доплаты, и это будет максимум, который может получить объявлени. Остальные получают по своим потребностям. Те, кто доплачивает, доплачивают столько, сколько заявили.
Например, 5 участников. 1-й хочет получить 100, 2-й 20, 3-й 50. 4-й и 5-й готовы отдать по 100.
Мы ищем обмены от объявления 1-го.
100+100-100-20-50=30
Значит 1-й получает 130.

Способ №2. Пропорциональный расчет.

Но возможно, что имеет смысл распределять суммы пропорционально чтобы вариант обмена выглядел одинаково для всех объявлений от которых можно начать строить цепочку.
Мы высчитываем остаток между предлагающимися доплатам и требующимися доплатами и распределяем его пропорционально между теми, кому требуются деньги.
Например, 5 участников. 1-й хочет получить 100, 2-й 20, 3-й 50. 4-й и 5-й готовы отдать по 100.
Мы ищем обмены от 1-го.
Ищем остаток: 100+100-100-20-50=30
Находим долю 1-го в требуемых суммах: 100/(100+20+50)*100=58,82
Ищем 58,82 от остатка 30: 30*0,5882=17,646
Увеличиваем на эту сумму то, что получит 1-й: 100+17,646=117,646
Для 2-го и 3-го также рассчитываем их суммы.
4-й и 5-й отдают столько, сколько предложили.

Способ №3. Минимальный достаточный расчет.

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

Если предлагаемых денег на всех не хватает. Объявление, от которого строим цепочку, желает получить доплату.

Способ №1. Объявлению, от которого строим цепочку, показываем максимум, который оно может получить, если все остальные получат сначала то, что они хотят. Т.е. даем 1-му остаток, если что-то остается.

Например, 5 участников. 1-й хочет получить 100, 2-й 20, 3-й 50. 4-й и 5-й готовы отдать по 50. 50+50-20-50=30. Значит 1-й получит только 30.
Если же ничего не достается и остаток отрицательный, то тогда отображать ему, что он должен доплатить этот остаток.

Способ №2. Пропорциональный расчет.

Если остаток отрицательный (т.е. на всех денег не хватает), то мы высчитываем пропорцию этого остатка в общей сумме, которая требуется. И уменьшаем сумму, которая достанется объявлению от которого строим цепочку, пропорционально. Например, 5 участников. 1-й хочет получить 100, 2-й 20, 3-й 50. 4-й и 5-й готовы отдать по 50.
Мы ищем обмены от 1-го.
Ищем остаток: 50+50-100-20-50=-70
Находим долю 1-го в требуемых суммах: 100/(100+20+50)*100=58,82
Ищем 58,82 от остатка -70: 70*0,5882=41,174
Уменьшаем на эту сумму то, что получит 1-й: 100-41,174=58,826
Ее и выводим в блоке "1-й получает" для 1-го.

Способ №3

В этих условиях он отсутствует. Требуют денег больше, чем предлагается в цепочке.

Объявление, от которого строим цепочку, желает доплатить.

Если объявление желает доплатить, то считаем для него минимум, который получится по аналогичным алгоритмам.
Например, 5 участников. 1-й хочет получить 100, 2-й 20, 3-й 50. 4-й и 5-й готовы отдать по 100.
Мы ищем обмены от 3-го.
100+20+50-100=70
Значит 3-й отдает 70.

Если общей суммы не хватает чтобы всем раздать, то тоже можем увеличить вклад 3-го пропорционально, или на всю сумму. по аналогии с предыдущими алгоритмами.