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
Post a Comment