search

JamesBremner / so76213744

Code for https://stackoverflow.com/q/76213744/16582
0 stars 0 forks source link

Misunderstanding of the stackoverflow answer #2

Open kyssadin opened 1 year ago

kyssadin commented 1 year ago

I think you misunderstood the task I was describing on StackOverflow. Let me rephrase the task.

There's a set of cities. Each city has an interest value. The goal is to find a tour of a given set of cities so that the sum of the interest values is maximized. There's a budget constraint. The edges are marked with the costs of travelling through them, not the distances between the nodes ( I guess this part is what got you confused ) . All the cities are connected with each other. Visiting 1 city twice is not allowed, unless you need to return to the first one. Visiting all the cities is not necessary, the main goal is to get the max interest value sum and return to the starting city. The answer should contain the path itself, the sum of interest values, and the money left.

The thing is, you have covered the default TSP with your implementation, but my task requires to maximize the interest values and return back to the first city.

JamesBremner commented 1 year ago

you have covered the default TSP with your implementation

Yes. It is the best place to start.

my task requires to maximize the interest values and return back to the first city.

Read the full algorithm I posted to stackoverflow, which if you implement it ( using my code if you like for the tricky part ) will solve your problem. Once you have TSP solved, the rest of the algorithm is trivial to implement.

kyssadin commented 1 year ago

Ok thank you so much for your time. I will try to come up with something. If I will have any more questions, may I contact you again?

JamesBremner commented 1 year ago

Do you understand the algorithm I posted? Do you agree that it will solve your problem?

JamesBremner commented 1 year ago

No answer :-(

Well, like I said the rest of the algorithm is trivial to implement. So, here it is:

https://github.com/JamesBremner/so76213744/blob/ec504fcf2d3d7f8d2c995d16aae252e025c07977/src/main.cpp#L52-L79

Here is output when the budget is 500

Dropping e ( 6 ) from itinerary
Dropping c ( 7 ) from itinerary
Minimum cost : 200 Budget : 500
Path Taken : a b d

I have added the budget and the city interest levels specification to the input file. The new format is documented here https://github.com/JamesBremner/so76213744/wiki/Input-File-Format