First, thanks for the great explanation and discussion!
There is one step I would have liked you to discuss a bit more: How does one reason about turning a recurrence relationship into a fill-order. A recurrence is top-down, whereas filling is bottom-up, and there is some reasoning behind the fill-order that is related to avoiding a cache-miss etc.
Also, as others have pointed out, you still have several mistakes in the text regarding the museum variant. I think you might have fixed some, but there are still at least three remaining.
K(i, w) = max(K(i - 1, w - wi) + vi, K(i - 1, w - wi))
"We do not add the current item: K(i - 1, w - wi)"
"we simply follow the K(i - 1, w - wi) path"
These should all say K(i - 1, w) instead of K(i - 1, w - wi), however in (1), only the the second argument to max is wrong, the first is correct.
Also, I think "subsect" should be "subset".
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
First, thanks for the great explanation and discussion!
There is one step I would have liked you to discuss a bit more: How does one reason about turning a recurrence relationship into a fill-order. A recurrence is top-down, whereas filling is bottom-up, and there is some reasoning behind the fill-order that is related to avoiding a cache-miss etc.
Also, as others have pointed out, you still have several mistakes in the text regarding the museum variant. I think you might have fixed some, but there are still at least three remaining.
These should all say K(i - 1, w) instead of K(i - 1, w - wi), however in (1), only the the second argument to
max
is wrong, the first is correct.Also, I think "subsect" should be "subset".