## Monday, August 29, 2016

### [TopCoder]SRM 647 Div2 Travelling Salesman Easy

[TopCoder]SRM 647 Div2 Travelling Salesman Easy | 书影博客
You are a traveling salesman. You have already heard a lot about how hard the problems of a traveling salesman can be. Luckily, the one you currently have seems easier.
There are M cities where you can sell products. The cities are conveniently numbered 1 through M.
You have a case that contains multiple items. Each of those items can only be sold in one of the cities. You are given information about those items in tuple (integer)s profit and city. For each valid i, you have an item that can be sold in city[i], and doing so would bring you profit[i] dollars of profit. Obviously, you can only sell each item at most once.
You have already planned your business trip: a sequence of cities you are going to visit. These are given in the tuple (integer) visit. Each time you visit a city you may sell at most one item.
Compute and return the maximum total profit you can obtain.

def getMaxProfit(self, M, profit, city, visit): items = [[] for i in range(M)] size = len(profit) for i in range(size): items[city[i] - 1].append(profit[i]) for i in range(M): items[i] = sorted(items[i], reverse = True) profit = 0 for c in visit: if len(items[c - 1]): profit += items[c - 1][0] items[c - 1].pop(0) return profit