Can we accommodate two items in the same weight so that we could maximize the value? - Nope.the previous row* has 0 in it, since we were not able able accommodate Item 1 in weight 4. Is the value for the current weight is higher without Item 2? - Check the previous row for the same weight.Can we accommodate Item 2 - Yes, we can.So, it is kind of intuitive that the rest of the row will just be the same value too since we are unable to add in any other item for that extra weight that we have got.Ĥ) So, the next interesting thing happens when we reach the column 4 in third row. Let’s fill in 10 there (remember, this is a Value array)ģ) Moving on, for weight 6 (column 6), can we accommodate anything else with the remaining weight of 1 (weight - weight of this item => 6 - 5). In fact, we wouldn’t be able to fill in anything until we reach the column 5 (weight 5).Ģ) Once we reach column 5 (which represents weight 5) on the first row, it means that we could accommodate item 1. What does row 1 and column 1 mean? That given the first item (row), can you accommodate it in the knapsack with capacity 1 (column). Nothing again !!! All zeroes.ġ) Now, let’s start filling in the array row-wise. What do you do hold in your knapsack if there are no items. It just means that there are no items in the house. So, let’s fill them up all with 0sīase case 2 : Let’s take the case of 0 row. It just means that the knapsack has 0 capacity. Let’s build an Item x Weight array called V (Value array) V = 4 rows * 10 columnsĮach of the values in this matrix represent a smaller Knapsack problem.īase case 1 : Let’s take the case of 0th column. The way this is optimally solved is using dynamic programming - solving for smaller sets of knapsack problems and then expanding them for the bigger problem. He either takes it or leaves it.Įxample : Knapsack Max weight : W = 10 (units)Ī cursory look at the example data tells us that the max value that we could accommodate with the limit of max weight of 10 is 50 + 40 = 90 with a weight of 7.

Obviously, he can’t split the table into half or jewellery into 3/4ths. To add fuel to the fire, the thief has an old knapsack which has limited capacity. There are fixed number of items in the home - each with its own weight and value - Jewellery, with less weight and highest value vs tables, with less value but a lot heavy. Here’s the general way the problem is explained - Consider a thief gets into a home to rob and he carries a knapsack. Given a Knapsack of a maximum capacity of W and N items each with its own value and weight, throw in items inside the Knapsack such that the final contents has the maximum value. I am sure if you are visiting this page, you already know the problem statement but just for the sake of completion Problem : I found the Knapsack problem tricky and interesting at the same time.

Knapsack problem explained