(972 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 remove an item from a vector element by remove_if [464 Views]
- How To Reset Autoincrement value of Column in MySQL [677 Views]
- Import Git project in Eclipse [316 Views]
- Mumbai University Theoretical Computer Science (TCS) Semester 4 Important Notes Download [599 Views]
- Prime Number program in Python [217 Views]

- Knuth-Morris-Pratt (KMP) Substring Search Algorithm with Java Example [9211 Views]
- Pseudocode and Algorithm to find whether number is Armstrong Number or Not [7540 Views]
- How To Win Ludo King Game Every Time [7342 Views]
- error: Multiple commands produce error in Xcode 10 [5048 Views]
- FlowChart and Pseudocode to find Whether a Number is Even or Odd [3990 Views]