Как мне найти наилучшую возможную комбинацию, которая дает самую низкую цену
Билеты:
- Один взрослый ($20)
- Один ребенок (один взрослый может привести только двух детей/дети не могут ходить одни) (12 долларов США)
- Один старший (16 долларов США)
- Семейный билет (до двух взрослых или пожилых людей и до трех детей) (60 долларов США на семью)
- Групповой билет (всего должно быть >= 6 человек) (15 долларов США на человека)
Если пользователь выбирает вариант 1 или 3, то запрашивается количество билетов и рассчитывается лучшая цена, поэтому в этом нет проблем.
Но когда они выбирают вариант 2, 4 или 5, то билеты для взрослых и детей запрашиваются для варианта 2, а билеты для взрослых, детей и пожилых людей запрашиваются для вариантов 4 и 5.
Поэтому я создал алгоритм, который работает только для некоторых сценариев, например (группа 4 взрослых 6 детей вместо этого станет 2 семейными билетами):
famticket = 0
groupticket = 0
famcost = 0
groupcost = 0
individualcost = 0
adultcount = ticketcount[0]
childcount = ticketcount[1]
while True:
if adultcount - 2 < 0 or childcount - 3 < 0:
if adultcount - 2 < 0 or childcount - 2 < 0:
leftovers[0] = adultcount
leftovers[1] = childcount
leftovers[2] = ticketcount[2]
break
else:
adultcount -= 2
childcount -= 2
famticket += 1
else:
adultcount -= 2
childcount -= 3
famticket += 1
famcost = famticket*ticketcost[len(chosendate)-1][3]
if sum(leftovers[0:3:2]) >= 6:
groupticket += sum(leftovers[0:3:2])
groupcost += ticketcost[len(chosendate)-1][4]* groupticket
leftovers[0],leftovers[2] = 0,0
individualcost += leftovers[1]*ticketcost[len(chosendate)-1][1]
else:
individualcost += leftovers[0]*ticketcost[len(chosendate)-1][0] + leftovers[1]*ticketcost[len(chosendate)-1][1] + leftovers[2]*ticketcost[len(chosendate)-1][2]
altcost = famcost + groupcost + individualcost
но в других сценариях, таких как (группа - 4 взрослых, 3 ребенка, 3 пожилых человека), это дает (2 взрослых и 3 пожилых индивидуальных билета и 1 семейный билет, который стоит 148 долларов США), но лучшая комбинация (7 групповых билетов и 3 индивидуальных детских билета, которые стоят 141 доллар США)
Так как же найти оптимальную комбинацию?
Ответы 1
Я бы попробовал разбить его на случаи
def best_price(adults,seniors,children):
if adults + seniors + children < 6:
# too small to get a group discount
return best_price_no_group(adults,seniors,children)
else:
# we can get a group discount but maybe its not best
price_without_groups = best_price_no_group(adults,seniors,children)
price_with_groups = best_price_groups(adults,seniors,children)
# return the "best" price out of both options
return min(price_with_groups,price_without_groups)
тогда я бы написал метод, чтобы найти лучшую цену, забыв, что у меня вообще есть какие-либо варианты для групп
в основном есть несколько случаев, когда использовать семейный пропуск дешевле, чем обычные проездные билеты
- Случай 1: Максимальная экономия: 2 взрослых проездных + 3 детских = 76,00 (рег.)
- Вариант 2: Довольно хорошая экономия: 1 взрослый + 1 старший + 3 ребенка = 72,00
- Вариант 3: Некоторая экономия: 2 взрослых билета + 2 ребенка = 64,
- Случай 4: Некоторая экономия: 2 пожилых человека + 3 ребенка = 68
- во всех остальных случаях дешевле ехать по индивидуальным пропускам
так что теперь просто кодифицируйте это
def best_price_no_groups(adults,seniors,children):
if adults >= 2 and children >= 3:
return 60 + best_price(adults-2,seniors,children-3)
if adults >= 2 and children >= 2:
return 60 + best_price(adults-2,seniors,children-3)
if adults == 1 and seniors >= 1 and children >= 3:
return 60 + best_price(adults-1,seniors - 1,children -3)
if seniors >= 2 and children >= 3:
return 60 + best_price(adults,seniors-2,children-3)
return adults*20 + seniors*16 + children*12
теперь напишите еще один метод, который имеет по крайней мере 6 человек для создания группы и может создать группу
то же самое... пройтись по логике, только на этот раз наоборот
когда групповая цена будет дороже
- СЛУЧАЙ 1: 1 взрослый + 5+ детей = (120+512)/6 = 80/6 = 13,33/чел.
- СЛУЧАЙ 2: 2 взрослых + 4+ детей = (60 + 1*12)/6 = 72/6 = 12/чел.
- СЛУЧАЙ 3: 2 пожилых + 4+детей = (60+12)/6 = 12/чел.
- СЛУЧАЙ 4: 1 Взрослый + 2 Старших + 3+детей = (16 + 60)/6 = 76/6 = 12,66/чел.
- СЛУЧАЙ 5: 2 взрослых + 1 старший + 3+детей = (16+60)/6
- СЛУЧАЙ 6: 1 старший + 5+ детей = (16 + 5*12)/6 = 76/6 = 12,66/чел.
- СЛУЧАЙ 7: 3 пожилых + 3+ детей = (16 + 60) = 76/6
- СЛУЧАЙ 8: 3 взрослых + 3+ детей = (20 + 60) = 80/6
Во всех остальных случаях будет дешевле использовать групповой пропуск с максимально возможным количеством взрослых, заполняя все дополнительные места пожилыми людьми и, в крайнем случае, детьми.
вы можете в основном упростить все эти случаи до
- если у вас 3 или менее взрослых и пожилых людей, без групп будет дешевле
- если у вас 4 или более взрослых и пожилых людей, это будет дешевле с группами
так что теперь мы можем реализовать это
def best_price_groups(adults,seniors,children):
if (adults+seniors+children) < 6:
# moot .... not enough for a group
return best_price_no_group(adults,seniors,children)
if children == 0:
# group price is always best when there are no children in the group
return (adults+seniors)*15
if (adults+seniors) < 4:
# cheaper to take advantage of family deal or no discounts
return best_price_no_group(adults,seniors,children)
if (adults+seniors)>=6:
# if we can use all adults and seniors in group and no children
return (adults+seniors)*15+children*12
else:
# if we have to include a couple kids thats ok i guess...
return 6*15 + 12*(children - (6- (adults+seniors)))
Я думаю, что это покрывает это ./.. я на самом деле не проверял это, поэтому вам могут понадобиться некоторые настройки