0% completed
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
On this page