(3635 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 |

- How To Count Number of Vowels, Consonants, Digits And Spaces In A Sentences Using C++ Program [356 Views]
- Rat in A Maze Problem Algorithm and Flowchart [1710 Views]
- Find HCF and LCM using Python [1405 Views]
- Counting Sort Algorithm with implementation in Java and Python [664 Views]
- Infix to Prefix notation Algorithm and Flowchart [518 Views]

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