I'm currently working on a calculator which splits up money. For example my friends and I go on vacation for 5 days. Everybody pays something for the group but not everybody is there the full 5 days. One friend is only two days there, another one is three days, another two are 4 days and the rest is there everyday. I already got to the part where I know who gets how much money and who needs to pay how much money. Now I "only" need to figure out who needs to pay who with the least transactions. I have an array of positive numbers:

```
40 => 68.25($)
42 => 44.25($)
49 => 28.75($)
41 => 24.25($)

```

and an array of negative numbers:

```
50 => -80.5($)
48 => -57.5($)
43 => -27.5($)

```

The key of these arrays are just and id's. So I know which value belongs to which friend. The positive numbers should get payed and the negative numbers need to pay. If you sum up the values from each array you get the same result except the sum of the negative array is negative, obviously.

My question now is how do I get the transactions so that in the end everybody gets or pays the right amount?

Thanks in advance for your ideas.