0
$\begingroup$

Based on this video, the tutor explains the knapsack problem with dynamic programming approach. One thing is not cleared in this video, which is my main question.

All the values on the first row (except 0) are set to 1 because value and weight (on that row) are 1 hence, we cannot exceed that number

Below is the complete example of the tutor as linked in the above video. enter image description here

My question:

-What would be the values of the first row if weight and value were not both the same?

So let's say value is 25 and weight 3 (first row values): I suppose the first row results would be 0,25,25,25,25,25,25,25

Let me know if i am wrong. Thank you.

Note that the first row is important to be correct as every row depends on the previous one. The tutor's example in the video, is not the best as the first row value and weight are both 1.

$\endgroup$
2
$\begingroup$

First row indicates the optimal knapsack for each weight using only that item. Then each subproblem in that row asks what is the maximal value one can reach with using only first item and maximum weight indicated by the columns. Then because your first item would have a weight of 3, there is no way for you to include an item for any total knapsack of weight less than 3. Therefore the optimal knapsack for each weight less than 3 would be 0.

Then the first row would look like: 0 0 0 25 25 25 25 25

$\endgroup$
  • $\begingroup$ Do you have a question why the above suggested is not correct? Important part here is not being correct or not. It is to understand why a solution might be correct or not. $\endgroup$ – sunnytheit Mar 18 '18 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.