Rekursion mit 1D-Array

Question

Ich habe dieses Problem stundenlang angeguckt. Aus irgendeinem Grund verstehe ich Flut füllen und Rekursion mit 2-D-Arrays, aber kann nicht scheinen, überhaupt zu diesem Problem zu starten:

Sie haben drei Assistenten für Sie arbeiten. Einer heißt Jeff, der andere heißt Jeff und der dritte heißt Jeff. Sie tippen alle mit der gleichen Geschwindigkeit von einer Seite pro Minute. Sie sind heute mit einem Bündel Papiere in Ihr Büro gekommen, die Sie so schnell wie möglich tippen müssen. Sie müssen die Papiere so unter Ihren Assistenten verteilen, dass sie alle Papiere zum frühestmöglichen Zeitpunkt fertigstellen. "Jeff, mach das", schreist du. "Jeff, mach das", sagst du. "Jeff, beende den Job", mahnest du. Also Jeff. Aber du musst ihm helfen. Also hast du diese APT.

Ihre Aufgabe ist, geben Sie eine int [] mit der Anzahl der Seiten für jedes Papier, geben Sie die minimale Anzahl von Minuten zurück, die Ihre Assistenten benötigen, um alle diese Papiere zu tippen. Angenommen, sie können ein Papier nicht in Teile aufteilen, dh jedes Papier wird von einer Person eingegeben. Zum Beispiel, gegeben {1,2,3,4,5,6,7}, sollte die Funktion 10 zurückgeben, weil 7 + 3 = 10, 6 + 2 + 1 = 9 und 5 + 4 = 9 (es gibt auch andere Kombinationen dieser Zahlen, die das gleiche Ergebnis liefern würden).

Answer 1

Ihre Aufgabe besteht hauptsächlich darin, das Partitionsproblem zu lösen.

https://en.wikipedia.org/wiki/Partition_problem

Seit dieser Aufgabe ist NP-vollständig ist, kann es nicht in Polynomialzeit gelöst (optimal) werden. Die Lösung kann nur angenähert werden.

Simplest apprach würde der Greedy-Algorithmus sein:

Zuerst Sie die Tabelle sortieren in absteigender Reihenfolge. Danach iterieren Sie darüber und weisen den Jeffs Aufgaben zu, denen bisher die geringste Arbeit zugewiesen wurde.

Keine Rekursion erforderlich.