Wie erstellt man einen Algorithmus, um Werte von Geld fair zwischen n Personen zu verteilen?

Question

Ich muss einen Algorithmus erstellen, um Geld unterschiedlicher Werte zwischen einer festen Anzahl von Personen zu verteilen. Die Geldmengen können nicht aufgeteilt werden.

Beispiel: Ich habe vier Geldbeträge: US $ 10, US $ 20, US $ 50 und US $ 90. Was ist der beste Weg, dieses Geld zwischen zwei Freunden so zu verteilen, dass sie einen fairen Wert haben? Es ist: der Unterschied zwischen den Werten ist am geringsten.

Für diesen Fall wäre die beste Lösung: Freund # 1: US $ 10, US $ 20 und US $ 50 (insgesamt = US $ 80). Freund # 2: US $ 90.

Wie könnte ich anfangen?

Hinweise: Alle Geldmengen müssen verteilt werden. Die Anzahl der Personen kann variieren.

Ich muss es in Java implementieren.

Answer 1

Sie können Brute-Force für O (k^n) oder dp für O (k^{2} * MAXSUM^{k - 1}) verwenden. Ich denke nicht, dass es möglich ist, es schneller zu lösen. (n ist die Anzahl der Münzen und k ist die Anzahl der Personen).