(3372 Views)

Before diving into the main 0/1 knapsack problem, lets first know about the original knapsack problem. In a knapsack problem, you have a knapsack which has a limited space available. There are couple of items with different value and space. You need to select those items which fits in the knapsack and their value is maximum.

Say you have a knapsack which can handle 5KG weight, and you have 4Kg gold, 3kg silver and 7Kg bronze. Since we have to maximize the value, we have to take 4Kg of gold as its value is maximum. We are left with 1Kg space, here we can put 1Kg silver. Now our knapsack is full and we have the maximum value products.

In both the problems, aim is the same, but there's a little difference. In fractional knapsack, we are allowed to select a fraction of the element, and in 0/1 knapsack, we can either select that element, or completely reject it. Fractional knapsack problem is rather easy and can be solved using greedy approach, whereas 0/1 knapsack problem is quite tricky and requires a dynamic approach.

In this problem, we have a size of knapsack (W), n elements and each element e_{i}, has a value v_{i} and weight w_{i}. Lets say our knapsack has size W and these are the elements available to us.

A recursive approach can be, select/deselect first element, then for each selection, select/deselect second element. But this method has a exponential time complexity. So we go for dynamic approach.

To solve this problem through dynamic approach, we'll take a 2d array, whose first dimensions will represent each item, and second dimension will represent weight of knapsack.

For weight(0), or knapsack of size 0, we can have 0 items of weight 0, 0 items of weight 3, 0 items of weight 4 and 0 items of weight 5.

Now for knapsack of size 1, we can have 1 item of size 1, and since we have only one item of each type, for higher weights knapsack also, we can accomodate only 1 item of type 1.

Now for item 2 having weight 3, since weight 1, 2 knapsack cannot accomodate this item, for 1 and 2 size, we'll have 1 element only. for knapsack of size 3, we have an option of selecting item1 or item2, since value of item2 is greater, we select item2 whose value is 4.

For knapsack size 4, we can have both item1 as well as item2, hence total value will be 5. Filling the second row in similar fashion.

Now for item3 having weight 4, we have to copy the value till knapsack limit 3, on knapsack weight 4, we have an option of selecting/rejecting this item. If we select this item, we'll get a value 5, and if we reject this item, then also we have 5, from above row. Hence we write 5. Filling this row in the same fashion.

We get this matrix after filling the last row

So item2 and item3 were selected to have total value of 9.

2 UpvotesUpvote |
0 DownvotesDownvote |

- Download DIGITAL SIGNAL PROCESSING by Ashok Ambardar PDF [1256 Views]
- Can a where Clause be used along with a Truncate command [716 Views]
- #undef directive in C Language [662 Views]
- Create a Custom Marker in Artoolkit [3184 Views]
- Can FOREIGN KEY column contain null value or duplicate values [538 Views]

- Algorithm to find whether number is Armstrong Number or Not [38408 Views]
- How To Win Ludo King Game Every Time [38200 Views]
- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [27140 Views]
- Jio Phone hang on LOGO problem Solution - Hard Reset Jio Phone [26932 Views]
- FlowChart and Algorithm to find Whether a Number is Even or Odd [19366 Views]