题目描述：

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.

题目大意：

你是一个旅行商人。你已经听很多人说过旅行商问题是一个很难的问题。幸运的是，你现在遇到的这个题目简单得多。

有M座城市可以销售商品，城市编号从1到M。

你有一个旅行箱，里边放了很多商品。每一件商品只能在一座城市销售。已知两个元组利润profit和城市city。对于每一个项目i，可以在city[i]销售，获得profit[i]的利润。显然，每个商品至多只能销售一次。

你已经计划好了你的旅行线路：一个你将要访问的城市的序列。这个序列以元组visit的形式给出。每一次你访问一座城市，至多只能销售一件商品。

计算利润的最大值。

解题思路：

贪心算法。

由于每件商品只能在某一座城市销售，因此每当访问一座城市时，只需选择在此城市可以获得最大利润的商品出售即可。

注意：如果商品可以在多个城市销售，上述贪心策略不可用。

Python代码：

class TravellingSalesmanEasy:
    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

 

本文链接：http://bookshadow.com/weblog/2015/01/25/topcoder-srm-647-div2-travelling-salesman-easy/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码