Ihr Generate-and-Test-Ansatz sollte für jeden Prolog-Programmierer mit mehr als ein paar Tagen Erfahrung verständlich sein. Hier sind einige kleine Verbesserungen:
%Vor%Ich habe go / 0 in go / 1 geändert, damit die Prolog-Engine alle Lösungen zurückführt (es gibt zwei). Die Aufrufe von length / 2 können weggelassen werden, weil totalCost / 4 die Arbeit zum Erstellen von Listenbeträgen so lang ist, dass sie mit Preisen identisch sind. Ich habe write / 1 und nl / 0 verwendet, um es etwas tragbarer zu machen.
In totalCost / 4 habe ich einige der Variablen- / Argumentnamen gekürzt und einen leicht jokey Namen für das Akkumulatorargument angenommen. Die Art und Weise, wie ich die Überprüfung durchführte, dass unser Akkumulator die gewünschte Summe nicht überschreitet, verwendet Ihren ursprünglichen Aufruf zu zwischen / 3 , aber mit einer berechneten oberen Grenze anstelle einer Konstante. Auf meinem Rechner wurde die Laufzeit von Minuten auf Sekunden reduziert.
Hinzugefügt: Ich sollte hier erwähnen, was in meinem Kommentar oben gesagt wurde, dass die Menüpunkte jetzt von den teuersten zu den wenigsten geordnet sind. Die Verwendung von SWI-Prologs Prädikat time / 1 zeigt, dass dies die Arbeit von 1.923 Rückschlüssen auf 1.070 Rückschlüsse reduziert. Die Hauptverbesserung (in der Geschwindigkeit) kommt von der Verwendung berechneter Grenzen auf A und nicht von Bereich 0 bis 10 für jedes Element.
%Vor%Beachten Sie die zusätzlichen Klammern um das zusammengesetzte Ziel, da andernfalls SWI-Prolog denkt, dass wir ein undefiniertes time / 2 Prädikat aufrufen.
Da Sie SWI-Prolog erwähnen, warum nicht
%Vor% und library(lambda)
Damit sind alle Variablen in der Liste Amounts in einem endlichen Bereich. Es besteht also keine Notwendigkeit, die obere Grenze zu berechnen (was sowieso oft schief geht).
Um konkrete Lösungen zu sehen, ist die Kennzeichnung / 2 erforderlich:
Tags und Links prolog clpfd np-complete