Ich möchte die Anzahl der Sterne bei einem bestimmten Budget und einer maximalen Begrenzung der Kombination maximieren.
Beispielfrage:
Mit einem Budget von 500 Euro, wenn Sie nur die maximal zulässigen Restaurants oder weniger besuchen, speisen und sammeln Sie die meisten Sterne, die möglich sind.
Ich möchte einen effizienten Algorithmus schreiben, der möglicherweise 1 Million Restaurantinstanzen für maximal 10 Restaurants verarbeiten kann.
Beachten Sie, dass dies ein Kreuzbeitrag aus einer Frage ist, die ich gestern gestellt habe: Java: Holen Sie sich die effizienteste Kombination einer großen Liste von Objekten basierend auf einem Feld
Die folgende Lösung weist dem r8
Restaurant 15 $ pro Stern zu , was bedeutet, dass beim Generieren der Liste diese zuerst in die Liste aufgenommen werden und mit den verbleibenden 70 $ nur 2 weitere Sterne erhalten werden, was insgesamt 4 Sterne ergibt. Wenn es jedoch klug genug wäre, das r8
Restaurant zu überspringen (obwohl es das beste Verhältnis von Dollar zu Stern ist), wäre das r1
Restaurant tatsächlich eine bessere Wahl für das Budget, da es 100 $ kostet und 5 Sterne kostet.
Kann jemand helfen, das Problem zu versuchen und die aktuelle Lösung zu schlagen?
import itertools
class Restaurant():
def __init__(self, cost, stars):
self.cost = cost
self.stars = stars
self.ratio = cost / stars
def display(self):
print("Cost: $" + str(self.cost))
print("Stars: " + str(self.stars))
print()
r1 = Restaurant(100, 5)
r2 = Restaurant(140, 3)
r3 = Restaurant(90, 4)
r4 = Restaurant(140, 3)
r5 = Restaurant(120, 4)
r6 = Restaurant(60, 1)
r7 = Restaurant(40, 1)
r8 = Restaurant(30, 2)
r9 = Restaurant(70, 2)
r10 = Restaurant(250, 5)
print()
print("***************")
print("** Unsorted: **")
print("***************")
print()
restaurants = [r1, r2, r3, r4, r5, r6, r7, r8, r9, r10]
for restaurant in restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("***************")
print("** Sorted: **")
print("***************")
print()
sorted_restaurants = sorted(restaurants, key = lambda x: x.ratio, reverse = True)
for restaurant in sorted_restaurants:
print(restaurant.ratio, restaurant.stars)
print()
print("*********************")
print("** Begin Rucksack: **")
print("*********************")
print()
max = 5
budget = 100
spent = 0
quantity = 0
rucksack = []
for i in itertools.count():
if len(rucksack) >= max or i == len(sorted_restaurants):
break
sorted_restaurants[i].display()
if sorted_restaurants[i].cost + spent <= budget:
spent = spent + sorted_restaurants[i].cost
rucksack.append(sorted_restaurants[i])
print("Total Cost: $" + str(sum([x.cost for x in rucksack])))
print("Total Stars: " + str(sum([x.stars for x in rucksack])))
print()
print("*****************")
print("** Final List: **")
print("*****************")
print()
for restaurant in rucksack:
restaurant.display()
budget
= maximales Rucksackgewicht in kg,max
= Anzahl der Gegenstände, die der Rucksack aufnehmen kann,stars
= ein gewisser Wert auf dem Gegenstand undcost
= Gegenstandsgewicht in kgr8
Restaurant 15 $ pro Stern zu , was bedeutet, dass es beim Generieren der Liste zuerst in die Liste aufgenommen wird und mit den verbleibenden 70 $ nur 2 weitere Sterne erhalten kann. Wenn es jedoch klug genug wäre, dies zu überspringen (obwohl es das beste Verhältnis von Dollar zu Stern ist, wäre dasr1
Restaurant tatsächlich eine bessere Wahl für das Budget, da es 100 $ kostet und 5 Sterne kostetAntworten:
Klingt so, als ob Ihr Problem fast dasselbe ist wie das Rucksackproblem: Maximieren Sie den Wert bei bestimmten Gewichts- und Volumenbeschränkungen. Grundsätzlich Wert = Gesamtsterne, Gewicht = Preis, Rucksacklimit = Gesamtbudget. Jetzt gibt es eine zusätzliche Einschränkung für die Gesamtzahl der "Artikel" (Restaurantbesuche), aber das ändert nichts am Kern.
Wie Sie vielleicht wissen oder nicht wissen, ist das Rucksackproblem NP-schwer, was bedeutet, dass kein Algorithmus mit Polynomzeitskalierung bekannt ist.
Es kann jedoch effiziente Pseudopolynomalgorithmen geben, die dynamische Programmierung verwenden, und natürlich gibt es effiziente Heuristiken, wie die "gierige" Heuristik, die Sie anscheinend entdeckt haben. Diese Heuristik beinhaltet, zuerst mit dem Auffüllen der Gegenstände mit der höchsten "Dichte" (die meisten Sterne pro Bock) zu beginnen. Wie Sie gesehen haben, findet diese Heuristik in einigen Fällen nicht das wahre Optimum.
Der dynamische Programmieransatz sollte hier ziemlich gut sein. Es basiert auf einer Rekursion: Was ist angesichts eines Budgets B und einer Anzahl verbleibender Besuche V die beste Gruppe von Restaurants aus einer Gesamtmenge von Restaurants R?
Siehe hier: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem
Grundsätzlich definieren wir ein Array
m
für "maximale Sterne", wobeim[i, b, v]
die maximale Anzahl von Sternen angegeben wird, die wir erhalten können, wenn wir Restaurants bis zur (einschließlich) Restaurantnummeri
, höchstens Ausgabenb
und höchstensv
Restaurants besuchen dürfen (das Limit). .Jetzt füllen wir dieses Array von unten nach oben. Zum Beispiel
m[0, b, v] = 0
für alle Werte vonb
undv
weil wir keine Sterne bekommen können, wenn wir nicht in ein Restaurant gehen können.Außerdem können wir
m[i, b, 0] = 0
für alle Werte voni
undb
weil wir keine Sterne mehr bekommen, wenn wir alle unsere Besuche aufgebraucht haben.Die nächste Zeile ist auch nicht zu schwer:
m[i, b, v] = m[i - 1, b, v] if p[i] > b
wop[i]
ist der Preis im Restaurant speiseni
. Was sagt diese Zeile? Wenn das Restauranti
teurer ist als wir noch Geld haben (b
), können wir nicht dorthin gehen. Was bedeutet, dass die maximale Anzahl an Sternen, die wir bekommen können, gleich ist, unabhängig davon, ob wir Restaurants bis zui
oder nur bis zu einbezieheni - 1
.Die nächste Zeile ist etwas knifflig:
m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b
Puh.
s[i]
ist die Anzahl der Sterne, die Siei
übrigens vom Restaurant erhalten.Was sagt diese Zeile? Es ist das Herzstück des dynamischen Programmieransatzes. Wenn wir die maximale Anzahl von Sternen berücksichtigen, die wir erhalten können, wenn wir uns Restaurants bis einschließlich
i
ansehen, dann gehen wir in der resultierenden Lösung entweder dorthin oder nicht, und wir müssen "nur" sehen, welcher dieser beiden Wege zu mehr führt Sterne:Wenn wir nicht ins Restaurant gehen
i
, behalten wir den gleichen Geldbetrag und die verbleibenden Besuche. Die maximale Anzahl an Sternen, die wir auf diesem Weg bekommen können, ist die gleiche, als hätten wir uns nicht einmal das Restaurant angeseheni
. Das ist der erste Teil in dermax
.Aber wenn wir ins Restaurant gehen
i
, haben wirp[i]
weniger Geld, einen Besuch weniger unds[i]
mehr Sterne. Das ist der zweite Teil in dermax
.Jetzt ist die Frage einfach: Welcher der beiden ist größer?
Sie können dieses Array erstellen und mit einer relativ einfachen for-Schleife füllen (lassen Sie sich vom Wiki inspirieren). Dies gibt Ihnen jedoch nur die Anzahl der Sterne, nicht die tatsächliche Liste der zu besuchenden Restaurants. Fügen Sie dazu der Berechnung von zusätzliche Buchhaltung hinzu
w
.Ich hoffe, dass Informationen ausreichen, um Sie in die richtige Richtung zu lenken.
Alternativ können Sie Ihr Problem in Form von binären Variablen und einer quadratischen Zielfunktion schreiben und auf dem D-Wave-Quanten-Annelaer lösen :-p Nachricht an mich, wenn Sie mehr darüber wissen möchten.
quelle
Mit der gleichen Idee wie meine Antwort hier :
Sie könnten die Liste ausgehend von den potenziell "billigsten" Restaurants erstellen .
Die Schritte des Algorithmus:
Natürlich können Sie ein Restaurant nicht erneut auswählen.
Ich denke, im schlimmsten Fall müssen Sie 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= ungefähr 12 Millionen) Lösungen berechnen.
In Javascript
quelle