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

Question

bounty到期在7天内。该问题的答案有资格获得+ 100声望赏金。AK47想要引起更多关注来回答这个问题。

在一定的预算和组合的最大限制下，我正在寻求最大数量的星星。

示例问题：

[预算为500欧元，只参观允许的最大餐厅或以下餐厅，用餐并收集尽可能多的星星。

我正在寻找一种有效的算法，该算法可以处理最多100个最大餐厅的100万个餐厅实例。

注意，这是我昨天问的一个问题的交叉帖子：Java: Get the most efficient combination of a large List of objects based on a field

下面的解决方案将为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()

我正在设法在给定预算和组合上限的情况下最大化星星数量。问题示例：预算为500欧元，仅访问允许的最大餐厅数量。...

Answer 1

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