Uzyskaj najbardziej wydajną kombinację dużej listy obiektów opartej na polu

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 r8restauracji, 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ąć r8restaurację (nawet jeśli jest to najlepszy stosunek dolara do gwiazdy), r1restauracja 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()

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ę mdla „maksymalnej liczby gwiazdek”, gdzie m[i, b, v]jest maksymalna ilość gwiazdek, jaką możemy uzyskać, kiedy możemy odwiedzać restauracje do (włącznie) liczby restauracji i, wydać co najwyżej bi odwiedzać większość vrestauracji (limit) .

Teraz oddolnie wypełniamy tę tablicę. Na przykład m[0, b, v] = 0dla wszystkich wartości bi vponieważ jeśli nie możemy iść do żadnej restauracji, nie możemy dostać żadnych gwiazdek.

Ponadto, m[i, b, 0] = 0dla wszystkich wartości ii bponieważ 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 gdzie p[i]jest cena posiłku w restauracji i. Co mówi ta linia? Cóż, jeśli restauracja ijest 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, iczy tylko do i - 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 restauracji ibtw.

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ęść w max.

Ale jeśli pójdziemy do restauracji i, pozostanie nam p[i]mniej pieniędzy, jedna wizyta i s[i]więcej gwiazdek. To druga część w max.

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.

Korzystając z tego samego pomysłu, co moja odpowiedź tutaj :

W zbiorze n liczb dodatnich, które sumują się do S, przynajmniej jedna z nich będzie mniejsza niż S podzielona przez n (S / n)

możesz zbudować listę, zaczynając od potencjalnych „najtańszych” restauracji .

Kroki algorytmu:

• Znajdź 5 restauracji o koszcie <500/10, każda z różnymi gwiazdkami i najniższym kosztem dla każdej gwiazdy . np. r1, r2, r3, r4, r5
• Dla każdej z powyższych wartości znajdź kolejne 5 restauracji o koszcie <(500 - koszt (x)) / 9 i różnych gwiazdkach . Ponownie wybierz najniższy koszt dla każdej gwiazdy
• rób to, aż dotrzesz do 10 restauracji i nie przekroczysz swojego budżetu.
• Uruchom ponownie powyższe 3 kroki, aby uzyskać limit 1–9 restauracji.
• Zachowaj rozwiązanie, które produkuje najwięcej gwiazd

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

function Restaurant(name, cost, stars) {
    this.name = name;
    this.cost = cost;
    this.stars = stars;
}

function RestaurantCollection() {
    var restaurants = [];
    var cost = 0;
    this.stars = 0;

    this.addRestaurant = function(restaurant) {
        restaurants.push(restaurant);
        cost += restaurant.cost;
        this.stars += restaurant.stars;
    };

    this.setRestaurants = function(clonedRestaurants, nCost, nStars) {
        restaurants = clonedRestaurants;
        cost = nCost;
        this.stars += nStars;
    };
    this.getAll = function() {
        return restaurants;
    };

    this.getCost = function() {
        return cost;
    };
    this.setCost = function(clonedCost) {
        cost = clonedCost;
    };

    this.findNext5Restaurants = function(restaurants, budget, totalGoal) {
        var existingRestaurants = this.getAll();
        var maxCost = (budget - cost) / (totalGoal - existingRestaurants.length);
        var cheapestRestaurantPerStarRating = [];
        for(var stars = 5; stars > 0; stars--) {
            var found = findCheapestRestaurant(restaurants, stars, maxCost, existingRestaurants);
            if(found) {
                cheapestRestaurantPerStarRating.push(found);
            }
        }
        return cheapestRestaurantPerStarRating;
    };

    this.clone = function() {
        var restaurantCollection = new RestaurantCollection();
        restaurantCollection.setRestaurants([...restaurants], this.getCost(), this.stars);
        return restaurantCollection;
    };
}

function findCheapestRestaurant(restaurants, stars, maxCost, excludeRestaurants) {
     var excludeRestaurantNames = excludeRestaurants.map(restaurant => restaurant.name);
     var found = restaurants.find(restaurant => restaurant.stars == stars && restaurant.cost <= maxCost && !excludeRestaurantNames.includes(restaurant.name));
     return found;
}

function calculateNextCollections(restaurants, collections, budget, totalGoal) {
    var newCollections = [];
    collections.forEach(collection => {
        var nextRestaurants = collection.findNext5Restaurants(restaurants, budget, totalGoal);
        nextRestaurants.forEach(restaurant => {
            var newCollection = collection.clone();
            newCollection.addRestaurant(restaurant);
            if(newCollection.getCost() <= budget) {
                 newCollections.push(newCollection);
            }
        });
    });
    return newCollections;
};

var restaurants = [];
restaurants.push(new Restaurant('r1', 100, 5));
restaurants.push(new Restaurant('r2',140, 3));
restaurants.push(new Restaurant('r3',90, 4));
restaurants.push(new Restaurant('r4',140, 3));
restaurants.push(new Restaurant('r5',120, 4));
restaurants.push(new Restaurant('r6',60, 1));
restaurants.push(new Restaurant('r7',40, 1));
restaurants.push(new Restaurant('r8',30, 2));
restaurants.push(new Restaurant('r9',70, 2));
restaurants.push(new Restaurant('r10',250, 5));

restaurants.sort((a, b) => a.cost - b.cost);
var max = 5;
var budget = 100;

var total = max;
var totalCollections = [];

for(var totalGoal = total; totalGoal > 0; totalGoal--) {
    var collections = [new RestaurantCollection()];

    for(var i = totalGoal; i > 0; i--) {
        collections = calculateNextCollections(restaurants, collections, budget, totalGoal);
    }
    totalCollections = totalCollections.concat(collections);
}

var totalCollections = totalCollections.map(collection => { 
      return {
          name: collection.getAll().map(restaurant => restaurant.name),
          stars: collection.stars,
          cost: collection.getCost()
      }
});

console.log("Solutions found:\n");
console.log(totalCollections);

totalCollections.sort((a, b) => b.stars - a.stars);
console.log("Best solution:\n");
console.log(totalCollections[0]);