I have a software problem and I'm searching for a solution but tried different algorithm approach and nothing came out. I'm not very familiar with all the graph algorithms and I hope there is already a way to solve this kind of problems in polynomial time.
I need the algorithm for different task but I illustrated simple like this: The are N cities and there is a wanderer. The time it takes for him to go from a town to another town is known - Txy (from town x to town y). >From any town he can go to another town so it is a complete graph. In each town there is a an amount of money Mx the wanderer wants to collect. It isn't enough time to pass through all cities. Having the total available time T and the starting point i, the problem is to find the best route so that the money he collects will be maximum. Input numbers range: N is between 400 and 600 Mx(M1, M2, ...) are between 50 and 500, x between 1 and N Txy are between 1 and 200, x and y are between 1 and N, x!=y T is between 1000 and 5000 The problems is shared here: http://www.evernote.com/shard/s119/sh/79f47a65-c1e6-44da-bbc0-7d10e36c7f71/374eda2f355c9a18d41ea19a20866fbc Thanks -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
