Chcę zmaksymalizować liczbę gwiazdek, biorąc pod uwagę określony budżet i maksymalny limit kombinacji.
Przykładowe pytanie:
Z budżetem 500 euro odwiedzając tylko maksymalną dozwoloną liczbę restauracji lub mniej, jedz i zbieraj jak najwięcej gwiazdek.
Chcę napisać skuteczny algorytm, który mógłby potencjalnie przetworzyć 1 milion wystąpień restauracji dla maksymalnie 10 restauracji.
Uwaga: to jest post z pytania, które zadałem wczoraj: Java: uzyskaj najbardziej wydajną kombinację dużej listy obiektów opartej na polu
Poniższe rozwiązanie przypisze 15 $ za gwiazdkę do r8
restauracji, co oznacza, że podczas generowania listy umieszcza ją najpierw na liście, a przy pozostałych 70 $ może uzyskać tylko 2 dodatkowe gwiazdki, dając w sumie 4 gwiazdki. Jednak jeśli byłoby wystarczająco inteligentne, aby pominąć r8
restaurację (nawet jeśli jest to najlepszy stosunek dolara do gwiazdy), r1
restauracja byłaby rzeczywiście lepszym wyborem dla budżetu, ponieważ kosztuje 100 $ i 5 gwiazdek.
Czy ktoś może pomóc rozwiązać problem i pokonać bieżące rozwiązanie?
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
= maksymalna waga plecaka w kg,max
= liczba przedmiotów, które może pomieścić plecak,stars
= pewna wartość przedmiotu icost
= waga przedmiotu w kgr8
restauracji, co oznacza, że podczas generowania listy umieszcza ją najpierw na liście, a przy pozostałych 70 $ może uzyskać tylko 2 dodatkowe gwiazdki. Jeśli jednak byłoby wystarczająco sprytne, aby to pominąć (chociaż jest to najlepszy stosunek dolara do gwiazdy,r1
restauracja byłaby rzeczywiście lepszym wyborem dla budżetu, ponieważ kosztuje 100 $ i 5 gwiazdekOdpowiedzi:
Wygląda na to, że twój problem jest prawie taki sam jak problem z plecakiem: Maksymalizuj wartość, biorąc pod uwagę pewne ograniczenia masy i objętości. Zasadniczo wartość = suma gwiazdek, waga = cena, limit plecaka = całkowity budżet. Teraz istnieje dodatkowe ograniczenie całkowitej liczby „przedmiotów” (wizyty w restauracji), ale to nie zmienia istoty.
Jak możesz wiedzieć, problem plecakowy jest NP trudny, co oznacza, że nie jest znany algorytm z wielomianowym skalowaniem czasu.
Jednak mogą istnieć wydajne algorytmy pseudopolinomalne wykorzystujące programowanie dynamiczne i oczywiście istnieją wydajne heurystyki, takie jak „chciwa” heurystyka, którą zdajesz się odkryć. Ta heurystyka polega na tym, że najpierw zaczyna się wypełniać przedmioty o największej gęstości (najwięcej gwiazdek na złotówki). Jak widzieliście, ta heurystyka w niektórych przypadkach nie znajduje prawdziwego optimum.
Dynamiczne podejście do programowania powinno być tutaj całkiem dobre. Opiera się na rekursji: Biorąc pod uwagę budżet B i liczbę pozostałych wizyt V, jaki jest najlepszy zestaw restauracji do odwiedzenia z całego zestawu restauracji R?
Zobacz tutaj: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem
Zasadniczo definiujemy tablicę
m
dla „maksymalnej liczby gwiazdek”, gdziem[i, b, v]
jest maksymalna ilość gwiazdek, jaką możemy uzyskać, kiedy możemy odwiedzać restauracje do (włącznie) liczby restauracjii
, wydać co najwyżejb
i odwiedzać większośćv
restauracji (limit) .Teraz oddolnie wypełniamy tę tablicę. Na przykład
m[0, b, v] = 0
dla wszystkich wartościb
iv
ponieważ jeśli nie możemy iść do żadnej restauracji, nie możemy dostać żadnych gwiazdek.Ponadto,
m[i, b, 0] = 0
dla wszystkich wartościi
ib
ponieważ jeśli wykorzystamy wszystkie nasze wizyty, nie będziemy mogli zdobyć więcej gwiazdek.Następny wiersz też nie jest zbyt trudny:
m[i, b, v] = m[i - 1, b, v] if p[i] > b
gdziep[i]
jest cena posiłku w restauracjii
. Co mówi ta linia? Cóż, jeśli restauracjai
jest droższa niż mamy pieniądze (b
), nie możemy tam iść. Co oznacza, że maksymalna liczba gwiazdek, jaką możemy uzyskać, jest taka sama, niezależnie od tego, czy uwzględniamy restauracje do,i
czy tylko doi - 1
.Następna linia jest nieco trudna:
m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b
Uff
s[i]
to ilość gwiazdek, które otrzymujesz z restauracjii
btw.Co mówi ta linia? To sedno dynamicznego podejścia do programowania. Rozważając maksymalną liczbę gwiazdek, jaką możemy uzyskać, patrząc na restauracje włącznie
i
, to w wynikowym rozwiązaniu albo tam idziemy, albo nie, i „po prostu” musimy zobaczyć, która z tych dwóch ścieżek prowadzi do więcej gwiazdy:Jeśli nie pójdziemy do restauracji
i
, zachowamy tę samą kwotę i pozostałe wizyty. Maksymalna liczba gwiazdek, które możemy zdobyć na tej ścieżce, jest taka sama, jakbyśmy nawet nie patrzyli na restauracjęi
. To pierwsza część wmax
.Ale jeśli pójdziemy do restauracji
i
, pozostanie namp[i]
mniej pieniędzy, jedna wizyta is[i]
więcej gwiazdek. To druga część wmax
.Pytanie jest proste: który z nich jest większy.
Możesz utworzyć tę tablicę i wypełnić ją stosunkowo prostą pętlą for (zaczerpnij inspiracji z wiki). Daje to tylko liczbę gwiazdek, a nie rzeczywistą listę restauracji do odwiedzenia. W tym celu dodaj dodatkowe obliczenia do obliczeń
w
.Mam nadzieję, że te informacje wystarczą, aby wyruszyć we właściwym kierunku.
Alternatywnie możesz napisać swój problem w kategoriach zmiennych binarnych i kwadratowej funkcji celu i rozwiązać go na kwantyle kwantowym D-Wave :-p Prześlij mi wiadomość, jeśli chcesz dowiedzieć się więcej na ten temat.
źródło
Korzystając z tego samego pomysłu, co moja odpowiedź tutaj :
możesz zbudować listę, zaczynając od potencjalnych „najtańszych” restauracji .
Kroki algorytmu:
Oczywiście nie można ponownie wybrać restauracji.
Myślę, że w najgorszym przypadku będziesz musiał obliczyć 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= około 12 milionów) rozwiązań.
W javascript
źródło