Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
There is a bug in the diagram/algorithm in the section "How can we find the sele...

DarkStar

Jul 10, 2022

There is a bug in the diagram/algorithm in the section "How can we find the selected items?"

When you realize dp[i][c] != d[i-i][c] and you decide to include the current index in the final path, you actually have to go up a row - NOT stay in the same row.

For example, assume that the capacity is 6 instead of 7. You start at 17 in row D. You see the same as the row above, so you go to row C. Since that 17 is not the same as the row above, you take it.

Solution so far: C

Then subtract the weight of the current row (3) and that takes you to weight 10 on the same row. That's not the same as the row above...so you include C again?

What you have to do is subtract the weight and go to the row above (in this case row B)

1

0

Comments
Comments

On this page