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

- List all files in Amazon S3 bucket [126 Views]
- Java Serialization with Externalizable and their difference [166 Views]
- Tutorial to connect Android device to adb over mobile carrier network - 3G / 4G [250 Views]
- java.util.Arrays Common Used Methods [227 Views]
- Reading and Writing Images in Java using File streams [108 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [6566 Views]
- Pseudocode and Algorithm to find whether number is Armstrong Number or Not [5375 Views]
- How To Win Ludo King Game Every Time [5135 Views]
- error: Multiple commands produce error in Xcode 10 [4104 Views]
- Create Dynamic Pagination using Java Spring Boot, Hibernate and MySQL [3317 Views]