All geek questions in one place

What algorithm can be used to find the optimal solution for this?

I have accounts with positive and negative balance and interdependence between some. The pledge gives accounts with a negative balance the right to withdraw money from the pledge account to cover their losses.

I want to find the optimal procedure for invoking this right to receive money.

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

In this example, account A and B have a positive balance of 1000, and accounts 1,2,3 are covered by priority (1> 2> 3). I want to cover as many accounts as possible, distributing money A and B to 1,2,3, observing priority.

In this particular example, choosing A1 as my first pair will only result in coverage of 1000, but if I choose B1, A2, A3, I will have the optimal coverage solution of 2000.

What is the name of this optimization problem and what are the algorithms for solving it?

+4
source share
2 answers

This is basically a network flow issue. I draw a capacitive graph for your example (without a label, arcs have infinite capacitance). s is the source and t is the receiver.

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

The answer is not a maximum flow; this is a stream that maximizes 1, then 2, then 3. One multi-temporal algorithm is to modify the maximum stream algorithm based on additional paths (simple paths!), otherwise we could distract the stream from an account with a higher priority) to increase the paths through 1, then 2, then 3.

+4
source

My association says that you can find information in this area if "Packaging problems" (apply outside the geometry field)

I was not an expert in this field, I found the following topics that look relevant:

maybe even related:

+2
source

Source: https://habr.com/ru/post/1384126/

More articles:


All Articles