Obtenga la combinación más eficiente de una gran lista de objetos basada en un campo

Estoy buscando maximizar el número de estrellas dado un cierto presupuesto y un límite máximo en la combinación.

Pregunta de ejemplo:

Con un presupuesto de 500 euros, visitando solo los restaurantes máximos permitidos o menos, cena y recoge la mayor cantidad de estrellas posible.

Estoy buscando escribir un algoritmo eficiente, que potencialmente podría procesar 1 millón de instancias de restaurantes para hasta 10 restaurantes como máximo.

Tenga en cuenta que esta es una publicación cruzada de una pregunta que hice ayer: Java: obtenga la combinación más eficiente de una gran lista de objetos basada en un campo

La solución a continuación asignará 15 $ por estrella al r8restaurante, lo que significa que al generar la lista, primero la coloca en la lista, y con los 70 $ restantes solo puede obtener 2 estrellas más, lo que da un total de 4 estrellas. Sin embargo, si fuera lo suficientemente inteligente como para saltear el r8restaurante (a pesar de que es la mejor relación dólar por estrella), el r1restaurante en realidad sería una mejor opción para el presupuesto, ya que cuesta 100 $ y 5 estrellas.

¿Alguien puede ayudar a intentar el problema y superar la solución actual?

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()

Parece que su problema es más o menos lo mismo que el problema de la mochila: Maximice el valor dadas ciertas restricciones de peso y volumen. Básicamente valor = estrellas totales, peso = precio, límite de mochila = presupuesto total. Ahora hay una restricción adicional del total de "artículos" (visitas a restaurantes) pero eso no cambia la esencia.

Como puede saber o no, el problema de la mochila es NP difícil, lo que significa que no se conoce ningún algoritmo con escala de tiempo polinómica.

Sin embargo, puede haber algoritmos pseudopolinomiales eficientes que usen programación dinámica, y por supuesto, hay heurísticas eficientes, como la heurística "codiciosa" que parece haber descubierto. Esta heurística implica comenzar a llenarse primero con los elementos de "densidad" más altos (la mayoría de las estrellas por dólar). Como has visto, esta heurística no logra encontrar el verdadero óptimo en algunos casos.

El enfoque de programación dinámica debería ser bastante bueno aquí. Se basa en una recursividad: dado un presupuesto B y una cantidad de visitas restantes V, ¿cuál es el mejor conjunto de restaurantes para visitar de un conjunto total de restaurantes R?

Ver aquí: https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

Básicamente, definimos una matriz mpara "estrellas máximas", donde m[i, b, v]es la cantidad máxima de estrellas que podemos obtener cuando se nos permite visitar restaurantes hasta (e incluyendo) el número de restaurantes i, gastar como máximo by visitar en la mayoría de los vrestaurantes (el límite) .

Ahora, de abajo hacia arriba, llenamos esta matriz. Por ejemplo, m[0, b, v] = 0para todos los valores de by vporque si no podemos ir a ningún restaurante, no podemos obtener ninguna estrella.

Además, m[i, b, 0] = 0para todos los valores de iy bporque si utilizamos todas nuestras visitas, no podemos obtener más estrellas.

La siguiente línea tampoco es demasiado difícil:

m[i, b, v] = m[i - 1, b, v] if p[i] > b ¿Dónde p[i]está el precio de cenar en el restaurante i? ¿Qué dice esta línea? Bueno, si el restaurante ies más caro de lo que nos queda dinero ( b), entonces no podemos ir allí. Lo que significa que la cantidad máxima de estrellas que podemos obtener es la misma, ya sea que incluyamos restaurantes hasta io solo hasta i - 1.

La siguiente línea es un poco complicada:

m[i, b, v] = max(m[i-1, b, v]), m[i-1, b - p[i], v-1] + s[i]) if p[i] <= b

Uf. s[i]es la cantidad de estrellas que obtienes del restaurante por icierto.

¿Qué dice esta línea? Es el corazón del enfoque de programación dinámica. Cuando consideramos la cantidad máxima de estrellas que podemos obtener al mirar los restaurantes i, incluso en la solución resultante, vamos allí o no, y "solo" tenemos que ver cuál de estos dos caminos conduce a más estrellas:

Si no vamos al restaurante i, conservamos la misma cantidad de dinero y las visitas restantes. La cantidad máxima de estrellas que podemos obtener en este camino es la misma que si ni siquiera miramos el restaurante i. Esa es la primera parte de la max.

Pero si vamos al restaurante i, nos queda p[i]menos dinero, una visita menos y s[i]más estrellas. Esa es la segunda parte de la max.

Ahora la pregunta es simple: cuál de los dos es más grande.

Puede crear esta matriz y llenarla con un bucle for relativamente simple (inspírese en la wiki). Sin embargo, esto solo le da la cantidad de estrellas, no la lista real de restaurantes para visitar. Para eso, agregue un poco de contabilidad adicional al cálculo de w.

Espero que esa información sea suficiente para ponerlo en la dirección correcta.

Alternativamente, puede escribir su problema en términos de variables binarias y una función objetivo cuadrática y resolverlo en el annelaer cuántico D-Wave :-p Envíeme un mensaje si desea saber más sobre eso.

Usando la misma idea que mi respuesta aquí :

En una colección de n números positivos que suman S, al menos uno de ellos será menor que S dividido por n (S / n)

puede crear la lista a partir de los posibles restaurantes "más baratos" .

Los pasos del algoritmo:

• Encuentre los 5 restaurantes con un costo <500/10, cada uno con diferentes estrellas y el costo más bajo para cada estrella . por ejemplo, r1, r2, r3, r4, r5
• Para cada uno de los valores anteriores, encuentre otros 5 restaurantes con costo <(500 - costo (x)) / 9 y diferentes estrellas . Nuevamente seleccione el costo más bajo para cada estrella
• haga esto hasta llegar a 10 restaurantes y no exceda su presupuesto.
• Vuelva a ejecutar los 3 pasos anteriores para el límite de 1 a 9 restaurantes.
• Mantenga la solución que produce más estrellas.

Por supuesto, no puede volver a seleccionar un restaurante.

Creo que en el peor de los casos, tendrá que calcular 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= aproximadamente 12 millones) de soluciones.

En 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]);