How do I find the best possible combination which gives the cheapest price

Question

The tickets are:

1. One adult ($20)
2. One child (one adult can only bring two children/children are not allowed to go by themselves) ($12)
3. One senior ($16)
4. Family ticket (up to two adults or seniors, and up to three children)($60 per family)
5. Group ticket (total people has to be >= 6) ($15 per person)

If the user chooses either option 1 or 3, then the amount of tickets is asked and best price is calculated so there is no problem in that.

But when they choose option 2 or 4 or 5, then both adult and child tickets is asked for option 2 and adult, child and senior tickets is asked for option 4 and 5.

So I have created an algorithm which only works for some scenarios like (group 4 adults 6 children will become 2 family tickets instead):

  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

but in other scenarios like (group - 4 adults 3 child 3 seniors) it gives (2 adult and 3 senior individual tickets and 1 family ticket which is $148) but best combination is (7 group tickets and 3 individual child tickets which is $141)

So how could you find the optimum combination?

Answer 1

I would try and break it up into its cases

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)

then i would write a method to find the best price forgetting that i have any option for groups at all

there are basically a few cases where it is cheaper to use a family pass than regular pricing passes

• Case1: Most Savings: 2 adult passes + 3 children = 76.00 (reg)
• Case2: Pretty Good Savings: 1 adult + 1 senior + 3 Child = 72.00
• Case3: Some Savings: 2 adult passes + 2 child = 64,
• Case4: Some Savings: 2 seniors + 3 children =68
• all other cases it is cheaper to go with individual passes

so now just codify it

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

now write another method that does have at least 6 people to make a group and can make a group

same thing... walk through the logic except in reverse this time

when will a group price be more expensive

• CASE 1: 1 adult + 5+ children = (120+512)/6 = 80/6 = 13.33/person
• CASE 2: 2 adult + 4+ children = (60 + 1*12)/6 = 72/6 = 12/person
• CASE 3: 2 Seniors + 4+children = (60+12)/6 = 12/person
• CASE 4: 1 Adt + 2 Seniors + 3+children = (16 + 60)/6 = 76/6 = 12.66/person
• CASE 5: 2 Adt + 1 Senior + 3+children = (16+60)/6
• CASE 6: 1 Senior + 5+ children = (16 + 5*12)/6 = 76/6 = 12.66/person
• CASE 7: 3 Seniors + 3+ Children = (16 + 60) = 76/6
• CASE 8: 3 Adults + 3+ Children = (20 + 60) = 80/6

All other cases will be cheaper to use a group pass with as many adults as you can, filling any extra spots with seniors, and as a last resort children

you can basically simplify all these cases to

• if you have 3 or less adults and seniors, it will be cheaper without groups
• if you have 4 or more adults and seniors it will be cheaper with groups

so now we can implement that

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

I think that covers it ./.. i havent actually tested it, so you might need some tweaks