Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Webinars
About Us

Edit
Reply




Edit

0-1 Knapsack problem | Face Prep

Published on 11 Mar 2020

Program to solve the 0-1 knapsack problem is discussed here. Given weights and values of n items, the task is to put these items in a knapsack of capacity W to get the maximum total value in the knapsack.In this problem, 0-1 means that we can either put the complete item in the knapsack or ignore it.


Consider the following example,


Input:


Number of items: 3


value and weight of items:


100  20

50    10

150  30


Size of the knapsack: 50


Output:


Maximum total value in the knapsack: 250


Explanation:


Weight = 20, value = 100

Weight = 10, value = 50

Weight = 30, value = 150

Weight = (20 + 10), Value = (100 + 50)

Weight = (20 + 30), Value = (100 + 150)

Weight = (10 + 30), Value = (50 + 150)

Weight = (20 + 10 + 30) > 50

The maximum among these is 

Weight = (20 + 30), Value = (100 + 150)

Weight = 50, Value = 250


This problem can be solved in two different ways.


Method 1: Naive recursive implementation of 0-1 Knapsack problem.We have to consider all the subsets of the items.


There can be two cases for each item:


  • Item is included in the optimal subset.
  • Item is not included in the optimal set.


Therefore, the maximum value that can be obtained from the given n items is the max of the following two values.


  • Maximum value obtained by (n-1) items and W weight (by excluding nth item).
  • Value of the nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (by including nth item).


If the weight of the nth item is greater than W, then the nth item cannot be included and case 1 is the only possibility.


Method 2: Dynamic Programming approach of 0-1 knapsack problem.


In this approach, same set of sub-problems are not considered again. It is avoided by creating a temporary array and proceeding to solve in a bottom-up manner.


The time complexity using this approach is O(n*W), where n is the number of items and W is the weight of the knapsack.


Program to solve 0-1 knapsack problem (Naive approach)


C
C++
Java
Python 3

Output
Input - Enter the number of items : 3 Enter the item's weight and its value 20 100 10 50 30 150 Enter the capacity of the knapsack : 50 Output: Maximum value in a 0-1 knapsack : 250


Program to solve 0-1 knapsack problem (Dynamic Programming approach)


C
C++
Java
Python 3

Output
Input - Enter the number of items : 3 Enter the item's weight and its value 20 100 10 50 30 150 Enter the capacity of the knapsack : 50 Output: Maximum value in a 0-1 knapsack : 250


Recommended Programs




If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in