FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

0/1 Knapsack Problem



Introduction

The 0/1 Knapsack Problem is one of the most important optimization problems solved using Dynamic Programming. The objective is to maximize the total profit without exceeding the capacity of the knapsack.

The name 0/1 means that every item has only two possible choices:

  • 0 → Do not include the item.
  • 1 → Include the item completely.

Unlike the Fractional Knapsack Problem, an item cannot be divided into smaller parts.

Problem Statement

Given n items, each having a weight and a profit, determine the maximum total profit that can be obtained without exceeding the capacity of the knapsack.

Real-Life Example

Suppose a traveler has a backpack that can carry only 15 kg. Several valuable items are available, but each item can either be taken completely or left behind. The traveler wants to maximize the total value without exceeding the bag's capacity.

Input Example

Item Weight (kg) Profit (₹)
1 2 12
2 3 10
3 5 20
4 7 15

Knapsack Capacity = 10 kg

Possible Selections

Selected Items Total Weight Total Profit
1 + 2 5 22
1 + 3 7 32
2 + 3 8 30
2 + 4 10 25
1 + 2 + 3 10 42 (Optimal)

Why Dynamic Programming?

The same combinations of items are evaluated repeatedly during recursion. Dynamic Programming stores the solutions of these overlapping subproblems, thereby avoiding repeated calculations and improving efficiency.

💡 Key Idea

For every item, only two choices are available:

  • Include the item.
  • Exclude the item.

The algorithm selects the option that gives the maximum profit while satisfying the weight constraint.

Recurrence Relation

The recurrence relation for the 0/1 Knapsack Problem is:

K(i,w) = max { Profit(i) + K(i−1, w−Weight(i)) , K(i−1,w) }

Here,

  • i = Current item
  • w = Remaining capacity
  • K(i,w) = Maximum obtainable profit

Working Principle

The Dynamic Programming solution builds a two-dimensional table where rows represent items and columns represent knapsack capacities. Each cell stores the maximum profit obtainable for that combination. The final answer is found in the last cell of the table. 


Items

      │

Include ?

 /           \

Yes          No

 │             │

Compute     Skip

 │             │

Maximum Profit

Figure 1 : Decision Process in 0/1 Knapsack

Dynamic Programming Algorithm

Knapsack(W, wt[], profit[], n) Step 1 : Create a DP table K[n+1][W+1]. Step 2 : Initialize the first row and first column with 0. Step 3 : For every item and every capacity: If Weight(i) <= Capacity Include = Profit(i) + K[i-1][Capacity-Weight(i)] Exclude = K[i-1][Capacity] Store Maximum(Include, Exclude) Else Copy K[i-1][Capacity] Step 4 : The last cell of the table contains the maximum profit.

Dynamic Programming Table (Illustration)

The following table illustrates how Dynamic Programming stores intermediate results. Each cell represents the maximum profit that can be obtained for a given number of items and knapsack capacity.

Items \ Capacity 0 2 4 6 8 10
0 0 0 0 0 0 0
Item 1 0 12 12 12 12 12
Item 2 0 12 12 22 22 22
Item 3 0 12 12 22 32 42
Item 4 0 12 12 22 32 42

Figure 2 : Dynamic Programming Table for 0/1 Knapsack

Complexity Analysis

Parameter Complexity Remarks
Time Complexity O(n × W) n = Number of items, W = Knapsack Capacity.
Space Complexity O(n × W) Required for storing the DP table.

Advantages of 0/1 Knapsack

  • Produces the optimal solution.
  • Avoids repeated computation of subproblems.
  • Efficient for medium-sized optimization problems.
  • Easy to understand using Dynamic Programming tables.
  • Widely used in resource allocation problems.

Limitations of 0/1 Knapsack

  • Requires additional memory for the DP table.
  • Execution time increases with knapsack capacity.
  • Not suitable for very large capacities without optimization.
  • Items cannot be divided into smaller parts.

Applications of 0/1 Knapsack

Application Description
Cargo Loading Selecting goods within vehicle capacity.
Investment Planning Selecting projects within available budget.
Memory Management Allocating limited memory efficiently.
Resource Allocation Optimal utilization of available resources.
Cloud Computing Efficient allocation of virtual machines and storage.

0/1 Knapsack vs Fractional Knapsack

0/1 Knapsack Fractional Knapsack
Item is either selected or rejected. Item may be selected partially.
Uses Dynamic Programming. Uses Greedy Method.
Produces an exact optimal solution. Produces an optimal solution using fractions.
Items cannot be divided. Items can be divided.

💡 Remember This

Fractional Knapsack → Greedy Algorithm

0/1 Knapsack → Dynamic Programming

This is one of the most frequently asked comparison questions in AKTU examinations.

Important Points

  • Each item has only two choices: Include or Exclude.
  • The problem satisfies Optimal Substructure.
  • It also contains Overlapping Subproblems.
  • The solution is obtained using a Dynamic Programming table.
  • Time Complexity is O(n × W).
  • The last cell of the DP table stores the optimal profit.

🎓 AKTU Examination Tip

AKTU examinations frequently ask students to construct the Dynamic Programming table, write the recurrence relation, determine the maximum profit and compare the 0/1 Knapsack Problem with the Fractional Knapsack Problem.

💼 Interview Corner

  • Why is the 0/1 Knapsack Problem solved using Dynamic Programming?
  • What is the difference between 0/1 Knapsack and Fractional Knapsack?
  • Explain the recurrence relation used in the 0/1 Knapsack Problem.
  • Why can't a Greedy Algorithm solve the 0/1 Knapsack Problem optimally?
  • What is the significance of the last cell in the DP table?

Summary

The 0/1 Knapsack Problem is one of the classic optimization problems solved using Dynamic Programming. By storing intermediate results in a DP table, it avoids repeated computations and guarantees the maximum possible profit without exceeding the knapsack capacity. It is widely used in resource allocation, memory management, investment planning and many other optimization applications.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com