current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote -2 down vote favorite
1

I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem:

The state wants to monitor traffic on a highway n miles long. It costs ci to install a monitoring device on mile i of the highway. The maximum distance between monitoring devices should not be more than d miles. That is, if there is a monitoring device on mile i, then there must be one monitoring device from mile i + 1 to mile i + d (or it is the case that i + d > n). The state wants a plan that will minimize the cost. Assume there is an array C[1..n] of costs.

Let vk be the cost of the best solution assuming a k mile highway and assuming a monitoring device on mile k. Given C and d, if the values of v1 through vk-1 are known, show how to determine the value of vk. You can write this mathematically, or provide pseudocode in the style of the book. Note you need to take into account all possible values of k from k = 1 to k = n.

I'm sure a problem similar to this will appear on the exam coming up and I'd like to at least know where to begin solving this, so any assistance is appreciated.

share|improve this question
up vote 1 down vote accepted

With any dynamic programming problem. The trick is realizing where you can condense a lot of possibilities into a fewer number of possibilities.

A brute-force approach to this problem would be to try every possible location for the monitoring devices, eliminate those possibilities which are illegal (distance is greater than d), and then find the one with the minimum cost.

To go from brute-force to dynamic programming, you have to find where a lot of possibilities are equivalent. You can do this if you realize that you don't have to know the details of where the monitoring stations are before any particular location, all you need to know is the minimum cost to get there. Based on this, you can start with the simplest case and work from there.

Starting with k=1. What is the cost? This one is easy because we know we have to put a device at location 1, and there aren't any previous locations, so v[1] = C[1].

What about k=2? If d=1, then we had to have a device at location 1, so the cost is v[1]+C[2]. If d=2, then we also have the possibility of not needing a device at a previous location, so the cost is just C[2]. We'll choose the possibility with the least cost that is valid and call this v[2].

What about k=3? Now we have to consider v[2]+C[3], v[1]+C[3], or just C[3]. Again, we choose the one with the least cost that is valid and call it v[3].

We can proceed in the same way until we reach location n.

share|improve this answer
    
Okay, that helps a fair bit. I'll keep trying. – WoernerBro Mar 26 at 4:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.