dynamic programming - confusion regarding the optimal solution in rod cutting -


I'm talking about the problem of famous rod cutting in CLRS two optimal equations given:

1: r [n] = maximum (p_n, r_1 + r_ {n-1}, ..., r_ {n-1} + r_1);

2: r [n] = maximum (p_i + r_ {n-1}, ..., p_ {n-1} + r_1);

I have been confused for some time about why the second equation is correct.

Suppose p_k + r_ {nk} is the maximum value, it is possible that a r_k exists: r_k + r_ {nk} & gt; P_k + r_ {nk}?

In this case, the second equation above is not correct.

Any help?

I do not know how to respond properly. I was the same illusion, so I Searched for, finally found here I do not get any answers, so I think we are too dumb or have not understood any solution properly. How ever have I come in the link ... Here is another explanation for me to understand that whatever they say, for any possible solution, it will always be a matter of fact that in the max there are some things which are given in the array. So what we do, include directly in our solution, repetition 1: r [n] = maximum (p_n, r_1 + r_ {n-1}, ..., r_ {n-1} + r_1); The solution can be in r2 + r (n-2), but in this repetition 2 times this solution can be in p1 + r (n-1). I know that there is no clear answer.

Comments

Popular posts from this blog

c - Mpirun hangs when mpi send and recieve is put in a loop -

python - Apply coupon to a customer's subscription based on non-stripe related actions on the site -

java - Unable to get JDBC connection in Spring application to MySQL -