Ich versuche, verschiedene Implementierungen für ein gebrochenes Rucksackproblem zu schreiben.
Dafür habe ich zwei Arrays:
Der Elementwert [n] entspricht Elementgewichten [n]. So können wir value_per_unit als:
berechnen %Vor%Ich brauche jetzt die 2 Arrays (Werte und Gewichte), die nach dem value_per_unit Array
sortiert werden sollenzB: Wenn
Dann
values_per_unit = [3.0, 2.0, 4.0]
und so lautet values_per_unit_sorted [2.0, 3.0, 4.0]
Ich brauche die Arrays für Werte und Gewichte:
Gibt es eine Möglichkeit, dies mit einfachen Lambda-Funktionen zu erreichen?
Ich kann immer noch so etwas machen, aber es scheint jedes Mal sehr ineffizient zu sein, wenn ich auf die Elemente zugreifen muss:
%Vor%In einer Zeile:
%Vor%Um zu erklären: Zippen Sie zuerst die Listen, um sie zu paaren.
%Vor%Sortieren Sie dann nach dem Quotienten aus Wert und Gewicht.
%Vor%Entpacken Sie sie schließlich wieder in separate Listen.
%Vor%Eine Alternative besteht darin, Tupel zu konstruieren, die explizit das Verhältnis als erstes Element enthalten.
%Vor%Ersteres scheint bei einigen schnellen Tests etwas schneller zu sein. Wenn Sie nach einem optimalen Algorithmus suchen, werden Sie wahrscheinlich Dinge ausrollen müssen und die Lösung wird nicht so prägnant sein.
Und um den Kommentar von @TomWyllie zu adressieren, können Sie, wenn Sie bereits die Liste der Verhältnisse haben, verwenden:
%Vor%Beachten Sie, dass diese beiden letzten Lösungen sich von der ursprünglichen Lösung unterscheiden, wenn zwei Paare das gleiche Verhältnis haben. Diese Lösungen werden sekundär nach Wert sortiert, während die erste Lösung die Elemente in der gleichen Reihenfolge wie die ursprüngliche Liste enthält.
Eine elegante Methode ist eine multidimensionale Liste mit den Werten und Gewichten:
%Vor%Verwenden Sie dann die Sortiermethode mit einem Wert geteilt durch das Gewicht als Schlüssel.
%Vor% Für eine explizitere (aber wohl weniger pythische) Lösung erstellen Sie eine Liste von Indizes, sortiert nach dem Wert in diesem Index in value_per_unit , und ordnen Sie values und weights entsprechend neu an .
Ausgaben:
%Vor% Sie können das aufräumen, indem Sie unnötige zusätzliche Schleifen mit zip und mit einem Generatorausdruck beseitigen;
Welche Ausgänge;
%Vor% Beachten Sie, dass diese endgültigen Werte tuples nicht lists sind. Wenn die Ausgabe wirklich eine Liste sein soll, sollte ein einfaches values, weights = map(list, (values, weights)) genügen. Du könntest das sogar in den einen Liner einwickeln, obwohl es zu diesem Zeitpunkt wahrscheinlich ziemlich schwer wird, dem zu folgen, was passiert.
Das Problem, das Sie haben, liegt daran, dass Sie für jedes Element ein berechnetes Feld verwenden (Element I wird den berechneten Wert values[I]/weights[I] haben).
Um dies zu lösen und es trotzdem extrem einfach zu halten, können Sie es in ein Tupel dieser Form verwandeln: ( calculated_value, (value, weight) ) , pro Element.
Mit diesem Ansatz ist es einfach zu lesen und zu verstehen. Sehen Sie sich die folgende Lösung an:
%Vor%Beachten Sie auch, dass ich die Schleife von Ihrem ursprünglichen Code geändert habe:
range(values) wurde in range(len(values))
Da der Bereich die Länge der Liste und nicht die Liste selbst benötigen würde.