Я стремлюсь максимизировать количество звездочек с учетом определенного бюджета и максимального предела комбинации.
Пример вопроса:
С бюджетом 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()
budget
= максимальный вес рюкзака в кг,max
= количество предметов, которое может вместить рюкзак,stars
= некоторое значение для предмета иcost
= вес предмета в кгr8
Ресторану 15 $ за звезду , что означает, что при создании списка он сначала помещает его в список, а с оставшимися 70 $ он может получить только еще 2 звезды. Однако, если бы он был достаточно умен, чтобы пропустить это (даже при том, что это лучшее соотношение доллара к звезде,r1
ресторан на самом деле был бы лучшим выбором для бюджета, так как он стоил 100 долларов и 5 звездОтветы:
Похоже, ваша проблема почти такая же, как и проблема с рюкзаком: максимизируйте значение с учетом определенных ограничений по весу и объему. В основном значение = общее количество звезд, вес = цена, предел рюкзака = общий бюджет. Теперь есть дополнительное ограничение общего количества «предметов» (посещений ресторана), но это не меняет сути.
Как вы можете знать, а может и не знать, проблема рюкзака сложна с точки зрения 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] > b
гдеp[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
, то у нас останется столько же денег и оставшихся посещений. Максимальное количество звезд, которые мы можем получить на этом пути, такое же, как если бы мы даже не смотрели в ресторанi
. Это первая часть вmax
.Но если мы пойдем в ресторан
i
, у нас останетсяp[i]
меньше денег, меньше посещений иs[i]
больше звезд. Это вторая часть вmax
.Теперь вопрос прост: какой из двух больше.
Вы можете создать этот массив и заполнить его относительно простым циклом for (черпайте вдохновение из вики). Это просто дает вам количество звезд, а не фактический список ресторанов для посещения. Для этого добавьте немного дополнительной бухгалтерии к расчету
w
.Я надеюсь, что этой информации достаточно, чтобы направить вас в правильном направлении.
В качестве альтернативы, вы можете написать свою задачу в терминах бинарных переменных и квадратичной целевой функции и решить ее на квантовом аннелере D-Wave :-p Напишите мне, если вы хотите узнать больше об этом.
источник
Используя ту же идею, что и мой ответ здесь :
Вы можете составить список, начиная с потенциальных «самых дешевых» ресторанов .
Шаги алгоритма:
Конечно, вы не можете выбрать ресторан.
Я думаю, что в худшем случае вам придется рассчитать 5x5x5 ... = 5 ^ 10 + 5 ^ 9 + ... + 5 ^ 2 + 5 (= около 12 миллионов) решений.
В JavaScript
источник