Link copied to clipboard. Share away!

Dismiss

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.

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

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**

×