StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POFinding dynamic algorithm to determine optimal sequence
text
Body
copied!<p>This is a homework problem given in the class, and I was wondering if I can get some help.</p> <p>The problem is that, there is an old man. And he is in a park. The park consist of <code>c_1, c_2, c_3, ....c_n</code> benches in a long single route, where <code>c_1</code> is closest to the old man, and <code>c_n</code> is the last bench that the old man wants to sit on.</p> <p>He can ideally travel 120 feet without using any help. However, more he travels than 120 feet, he will get tired easily, and less he travel, there is going to be a time disadvantage of sitting on the bench, and getting up. Therefore, for each walk, the penalty for the walk would be <code>(120-x)^4</code> where <code>x</code> is the length of the walk that he has traveled so far after the last time he took a rest on the bench. </p> <p>If benches are located each 120 feet apart, that would give him no penalty since he can just take a rest in every bench he encounters, and that will make 120 feet travel, with 0 penalty. Obviously, he can skip the bench, if he thinks he has not traveled 120 feet so far, but only 10 or 20 feet. </p> <p>The goal is to find an algorithm that gives him the minimum overall penalty in a way using dynamic programming with good time complexity. It does not matter how many times he has taken rest on the bench, but to find a bench list which gives the minimum overall penalty.</p> <p>Do you think it is possible to achieve better than O(n^2) time complexity? I think this is very similar to the coin problems, or american football scoring problems, but its '(120-x)^4' penalty for every single travel between 2 benches is giving me a headache. </p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload