title: Travelling Salesman Shipping Depreciating Items to Different Markets
body: <p>What would be a good heuristic to use to solve the following challenge?</p>
  
  <blockquote>
    <p>Quality Blimps Inc. is looking to expand their sales to other cities
    (N), so they hired you as a salesman to fly to other cities to sell
    blimps. Blimps can be expensive to travel with, so you will need to
    determine how many blimps to take along with you on each trip and when
    to return to headquarters to get more. Quality Blimps has an unlimited
    supply of blimps.</p>
    
    <p>You will be able to sell only one blimp in each city you visit, but
    you do not need to visit every city, since some have expensive travel
    costs. Each city has an initial price that blimps sell for, but this
    goes down by a certain percentage as more blimps are sold (and the
    novelty wears off). Find a good route that will maximize profits.</p>
  </blockquote>
  
  <p><a href="https://www.hackerrank.com/codesprint4/challenges/tbsp">https://www.hackerrank.com/codesprint4/challenges/tbsp</a></p>
  
  <p>This challenge is similar to the standard Travelling Salesman Problem, but with some extra twists: The salesman needs to track both his own travel costs and the blimps'. Each city has different prices which blimps sell for, but these prices go down over his journey. What would be a fast algorithm (i.e. n log n ) to use to maximize profit? </p>
  
  <p>The prices of transporting the items in a way makes the TSP simpler. If the salesman is in city A and wants to go to B, he can compare The costs of going directly to B vs. costs of going back to Headquarters first to pick up more blimps. I.e. is it cheaper to take an extra blimp to B via A or to go back in-between. This check will create a series of looped trips, which the salesman could then go through in order of highest revenue. But what would be a good way to determine these loops in the first place? </p>