[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.
Read full article from [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 profitRead full article from [TopCoder]SRM 647 Div2 Travelling Salesman Easy | 书影博客
