weigthed interval scheduling with fixed number of intervals

[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?

[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?

[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.

[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?

[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.

[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.

[katisss]

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

[katisss]

http://alldpalgos.blogspot.com/2008/12/dynamic-programming.html
similar and solved problem

[katisss]

http://alldpalgos.blogspot.com/2008/12/dynamic-programming.html similar and solved problem

In the end i think it describes the partion problem http://en.wikipedia.org/wiki/Partition_problem
Walking the least amout in each étape...