获取基于字段的大型对象列表的最有效组合

Question

在给定一定的预算和组合的最大限制的情况下，我希望最大限度地增加星星的数量。

示例问题：

预算为 500 欧元，只访问允许的最大餐厅或更少，用餐并收集尽可能多的星星。

我正在寻找一种高效的算法，它可能会处理 100 万个餐厅实例，最多 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()

Answer 1

听起来您的问题与背包问题几乎相同：在特定的重量和体积限制下最大化价值。基本上价值=总星级，重量=价格，背包限制=总预算。现在有一个额外的总“项目”限制（餐厅访问），但这并没有改变要点。

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

但是，可能存在使用动态规划的高效伪多项式算法，当然还有高效的启发式算法，例如您似乎已经发现的“贪婪”启发式算法。这种启发式方法涉及首先开始填充最高“密度”的项目（每美元最多的星星）。如您所见，在某些情况下，这种启发式方法无法找到真正的最佳值。

动态规划方法在这里应该很不错。它基于递归：给定预算 B 和剩余的访问次数 V，在所有餐厅 R 中，最适合访问的餐厅是哪一组？

请参阅此处：https : //en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

基本上，我们m为“最大星级”定义了一个数组， m[i, b, v]当我们被允许访问最多（并包括）餐厅数量i、最多消费和最多b访问v餐厅（限制）时，我们可以获得的最大星级数量是多少.

现在，我们自下而上地填充这个数组。例如， m[0, b, v] = 0对于所有的值b，并v因为如果我们不能去任何餐厅，我们不能让任何明星。

此外，m[i, b, 0] = 0对于所有的值i，并b因为如果我们用完了所有我们的访问，我们不能得到任何更多的星星。

下一行也不太难：

m[i, b, v] = m[i - 1, b, v] if p[i] > bp[i]在餐厅用餐的价格 在哪里i。这条线说什么？好吧，如果餐厅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，那么我们保留相同数量的钱和剩余的访问量。我们在这条路径上可以获得的最大星星数量与我们甚至没有查看 restaurant 一样i。这是max.

但是，如果我们真的去餐厅i，那么我们所剩的p[i]钱会更少，光顾的人会更少，s[i]星星也会更多。这是max.

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

您可以创建这个数组并用一个相对简单的 for 循环填充它（从 wiki 中获取灵感）。这只是给你星星的数量，而不是实际要参观的餐馆名单。为此，在 的计算中添加一些额外的簿记w。

我希望这些信息足以让您朝着正确的方向前进。

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