Learn the 0/1 Knapsack Problem using Dynamic Programming with problem definition, recursive formula, bottom-up algorithm, example, and complexity analysis.
0/1 Knapsack Problem Dynamic Programming Approach
Introduction
The 0/1 Knapsack Problem is one of the most important and classic problems in Dynamic Programming.
In this problem, a set of items is given, where each item has:
- A weight
- A profit (value)
A knapsack with a fixed capacity is also given.
Each item can be:
- Taken completely (1), or
- Rejected completely (0)
Fractional selection is not allowed, hence it is called the 0/1 Knapsack Problem.
Problem Definition
Given:
- Number of items = n
- Weight of each item = w[i]
- Profit of each item = p[i]
- Knapsack capacity = W
Objective:
To maximize the total profit without exceeding the knapsack capacity W.
Recursive Formula
To decide whether to include the ith item:
- If w[i] > W
→ The item cannot be included - Otherwise, we choose the maximum of:
- Not including the item
- Including the item
K(i,W)=max(K(i−1,W), p[i]+K(i−1,W−w[i]))K(i, W) = \max \big( K(i-1, W),\; p[i] + K(i-1, W – w[i]) \big)K(i,W)=max(K(i−1,W),p[i]+K(i−1,W−w[i]))
Boundary Conditions:
- K(0,W)=0K(0, W) = 0K(0,W)=0
- K(i,0)=0K(i, 0) = 0K(i,0)=0
Problems in Recursive Approach
The recursive solution has the following drawbacks:
- Same subproblems are solved repeatedly
- Overlapping subproblems are created
- Time complexity becomes exponential
Therefore, the recursive approach is inefficient for large inputs.
Dynamic Programming Approach (Bottom-Up)
In the Bottom-Up (Tabulation) approach:
- A 2-D table K[n+1][W+1] is created
- Each entry stores the solution of a subproblem
- Previously computed results are reused
- Recursive calls are avoided
Algorithm: 0/1 Knapsack Using Dynamic Programming
Knapsack(n, W)
Create table K[0..n][0..W]
for i = 0 to n
for w = 0 to W
if i == 0 or w == 0
K[i][w] = 0
else if weight[i] ≤ w
K[i][w] = max(
K[i−1][w],
profit[i] + K[i−1][w−weight[i]]
)
else
K[i][w] = K[i−1][w]
return K[n][W]
Example
Given:
- Weights = {2, 3, 4, 5}
- Profits = {3, 4, 5, 6}
- Capacity W=5W = 5W=5
Optimal Selection:
Items with weights 2 and 3
Maximum Profit:
3+4=73 + 4 = 73+4=7
Time and Space Complexity
- Time Complexity: O(n×W)O(n \times W)O(n×W)
- Space Complexity: O(n×W)O(n \times W)O(n×W)
Advantages of 0/1 Knapsack Problem Using DP
- Guarantees an optimal solution
- Avoids overlapping subproblems
- Efficient for moderate and large inputs
- Widely applicable in real-world optimization problems
Conclusion
The 0/1 Knapsack Problem is a classic and important application of Dynamic Programming.
Since it satisfies both overlapping subproblems and optimal substructure, Dynamic Programming provides an efficient solution.
This algorithm is extremely useful in scenarios where resources are limited and profit optimization is required.
Some More:
- POP- Introduction to Programming Using ‘C’
- DS – Data structure Using C
- OOP – Object Oriented Programming
- Java Programming
- DBMS – Database Management System
- RDBMS – Relational Database Management System
- https://defineinfoloop.blogspot.com/?m=1