Member Avatar for katisss

I have to find a cost optimal solution for staying on campsites.
It is kind of weigthed interval scheduling with a given number of intervals (nights).
I wonder how to tackle it, dynamic programmic will work for cost optimizatation gernerally but how to build in the restriction on the number of intervalls?

  • 2 Contributors
  • 8 Replies
  • 133 Views
  • 5 Days Discussion Span
  • Latest Post Latest Post by katisss

Recommended Answers

All 8 Replies

Member Avatar for katisss

So i can pick for example 4 out of a list C=[0,10,23,30,45,78,95,100]; the larger the distance the higher the cost. How can i interval schedule with given n intervals?

Member Avatar for Momerath

Not sure what the issue is. Just limit the dynamic method to n items in the proposed solution. If it's over n, you reject it as a failed solution.

Member Avatar for katisss

The solution needs to cover the entire range and must have n intervals.
How can i make sure these conditions are met and still get the minimal cost?

Member Avatar for Momerath

Still not getting the problem. Set up your dynamic solver. Have it run. If it ever gets to a solution that has more than n parts, reject that as a solution. If it ever gets to a point where there are no more choices and it is less than n, reject that as a solution.

You could just generate all the combinations for this as there are only 1680 to check, and it would be faster than doing a dynamic solution.

Member Avatar for katisss

Brute force solution is unlikely to be the assignment for an algorithm class. besides you can only choose intervals that touch so you have to strat where you left th enight before.

Member Avatar for katisss

How about sorting by size and trying with the smallest n intervals until you have a for the entire 100 km?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.