 Explore
Placement Prep Edit 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  