基于一个字段，获取一个大对象列表中最有效的组合

Question

我希望在给定预算和最大限制组合的情况下，最大化星级数量。

示例问题：

有500欧元的预算，只访问允许的最大餐厅数量或更少，用餐并收集最多的星级。

我希望编写一个高效算法，可以处理多达1百万个餐厅实例，最多可选择10个餐厅。

请注意，这是我昨天提出的问题的跨贴： Java：根据字段从大型对象列表中获取最有效的组合 下面的解决方案将为“r8”餐厅分配15美元/星，这意味着在生成列表时，它首先放在列表中，且剩余70美元只能再获得2颗星，总共4颗星。但是，如果足够聪明地跳过“r8”餐厅（即使它是最佳的每星美元比率），则“r1”餐厅实际上会是预算的更好选择，因为它的成本为100美元，具有5颗星。

有人能否帮忙尝试解决这个问题，并打败当前的解决方案吗？

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

- AK47

---

这是背包问题吗？抱歉，我看得不太仔细。 - Kenny Ostrom

这是背包问题的相同概念 -- budget表示最大背包重量（单位为公斤），max表示背包能够容纳的物品数量，stars表示物品的某个值，cost表示物品的重量（单位为公斤）。 - AK47

代码发布的问题是什么？ - OneCricketeer

@cricket_007 根据订单，它为r8餐厅分配了每颗星15美元的价格。这意味着在生成列表时，它首先将其放入列表中，并且剩下的70美元只能获得2颗星。然而，如果它足够聪明地跳过它（即使它是最佳的每颗星美元比率），r1餐厅实际上会是预算更好的选择，因为它的成本是100美元和5颗星。 - AK47

Answer 1

听起来你的问题跟背包问题差不多：在一定的重量和容量约束下，最大化价值。基本上价值=总星数，重量=价格，行囊限制=总预算。现在有一个额外的限制是总“物品”（餐厅访问次数），但这并不改变主旨。

也许你知道，背包问题是NP难题，这意味着没有已知的多项式时间缩放算法。

然而，可能存在使用动态规划的有效伪多项式算法，当然还有有效的启发式算法，比如你似乎已经发现的“贪婪”启发式算法。这种启发式算法涉及到首先用最高“密度”物品（每个美元的星星最多）填充。正如你所看到的，这种启发式算法在某些情况下无法找到真正的最优解。

动态规划方法在这里应该很好用。它基于递归：给定预算B和剩余访问次数V，从总餐厅R中访问哪些餐厅最佳？

参见此处：https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem 基本上，我们定义一个名为“max stars”的数组m，其中m[i, b, v]表示当我们被允许访问餐厅（包括）到餐厅编号i，最多花费b，并且最多访问v家餐厅（限制）时，我们可以获得的最大星数。

现在，我们从底部向上填充这个数组。例如，对于所有的b和v值，m[0, b, v] = 0，因为如果我们不能去任何餐厅，我们就不能获得任何星星。

同样，对于所有的i和b值，m[i, b, 0] = 0，因为如果我们用完了所有的访问次数，我们就无法获得更多的星星。

接下来一行也不太难：

m[i, b, v] = m[i - 1, b, v]如果p[i] > b，那么这一行的意思是什么？嗯，如果餐厅i更贵，我们剩下的钱不够了（b），那么我们就不能去那里。这意味着我们能获得的最大星级数无论是包括餐厅i还是只包括餐厅i-1都是相同的。

下一行有点棘手：

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

哎呀。顺便提一下，s[i]是你从餐厅i得到的星星数量。

这一行说了什么？它是动态规划方法的核心。当考虑到包括并且不超过 i 的餐厅时我们可以得到的最大星级数时，那么在结果中我们要么去那里，要么不去，并且我们“只需要”看看这两条路径中哪一条能够获得更多的星级：

如果我们不去餐厅 i ，那么我们保持相同的金额和剩余访问次数。我们可以在这条路径中获得的最大星级数与我们甚至没有去餐厅 i 时所获得的最大星级数相同。这是max中的第一部分。

但是如果我们去餐厅 i ，那么我们会剩下p [i]少的钱，少一个访问机会，以及s [i]更多的星级。这是max中的第二部分。

现在问题很简单：这两个中哪一个更大。

您可以创建此数组并使用相对简单的for循环填充它（从wiki中获取灵感）。但这只给您提供了星级数量，而不是要访问的实际餐厅列表。为此，在计算w时添加一些额外的记录。

---

我希望这些信息足以指引您走向正确的方向。

或者，您可以将问题用二进制变量和二次目标函数的形式编写，并在D-Wave量子退火器上解决它 :-p 如果想了解更多信息，请给我发消息。

- cadolphs

---

关于多项式时间，10家餐厅的最大值意味着可以通过暴力法解决问题，迭代所有高达10家餐厅的组合，并保留最佳组合，在O(n^10)时间内完成。现在，我也不想使用n = 10 ^ 6时运行O(n^10)算法，但它确实是多项式时间。 - kaya3

“10家餐厅”是真正固定的数字吗？还是只在上面的例子中固定，对于不同的例子可以更大？ - cadolphs

这是一个很好的问题，分析运行时间时应该泛化哪些问题参数并不清楚。当然，目前没有已知的在k中具有多项式时间复杂度的解决方案，但如果我们只对小的k感兴趣，那么这个结论相当薄弱。 - kaya3

“max” 餐厅数量可能会改变。这一次迭代它可能是10，下一次可能是5。 - AK47

@AK47 无论如何，我上面勾画的算法应该非常不错。多维数组的大小由您的预算、餐厅数量和访问次数确定，填写数组的一个条目只需要O(1)的时间，因此该算法的运行时间为O(RBV)。 - cadolphs

Answer 2

使用与此处的回答相同的思路：

在总和为S的n个正数集合中，至少有一个小于S/n（S除以n）

你可以从潜在的“最便宜”的餐厅开始构建列表。

算法步骤：

• 找到成本<500/10的5家餐厅，每家餐厅都有不同的星级和每个星级的最低成本。例如r1、r2、r3、r4、r5
• 对于上述每个值，找到其他5家成本<(500-cost(x))/9且星级不同的餐厅。再次选择每个星级的最低成本
• 重复以上步骤，直到找到10家餐厅并且不超过预算。
• 对1-9家餐厅限制重新运行上述3个步骤。
• 保留产生最多星级的解决方案。

当然，你不能重新选择餐厅。

我认为最坏的情况是你需要计算5x5x5...= 5^10 + 5^9 + ... + 5^2 + 5（大约1200万）个解决方案。

使用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]);

- Jannes Botis

---

嘿@Jannes Botis，对于100,000家餐馆需要27秒：https://repl.it/repls/StripedMoralOptimization 你认为有可能优化它以处理100万条记录吗？ - AK47

瓶颈在于findCheapestRestaurant()函数内的.filter()，你可以在创建餐厅后按成本对它们进行排序并使用.find()而不是filter()，因为只有第一个找到的才是最便宜的。我已经在链接中进行了更改。但我认为最好的解决方案是使用一个带有成本索引的数据库（例如mysql）来存储餐厅，这样你就可以用条件选择替换.filter()。 - Jannes Botis