Dynamic Programming & 0/1 Knapsack

Abhijeet Singh Rajput

@abhijeetsingh

Created

Dec 7, 2025

Last Modified

3 months ago

Dynamic Programming & 0/1 Knapsack

Dynamic programming is used to solve the optimisation problem.
Dynamic programming divides the given original problem into smaller, overlapped sub-problems.
Stepwise increasing the size of the sub-problem, it starts with the solution of smaller sub-problems and finally reaches the original initial problem. It records the solution of smaller sub-problems in a table.
The main idea of this approach is to develop a recurrence relation in which the solution of the current sub-problem relates with the solution of previous smaller sub-problems. This is called the recurrence equation.
In this way, the dynamic programming approach achieves the global Optima with the help of local Optima.
Dynamic programming works in a bottom-up essence and finally solves the original problem.

Applications of Dynamic Programming Approach

0/1 Knapsack problem
Optimal Binary Search Tree

Optimal Binary Search Tree is a kind of binary search tree in which the number of key comparisons is minimum in order of successful search of key.

0/1 Knapsack Problem

In 0/1 knapsack problem we have n items of known value and weight, and a knapsack of given capacity.
The objective is to find an optimal subset of the items in order to maximize the total profit earned but under the capacity constraint.

Items:

i = (1, 2, \cdot \cdot \cdot, i, \cdot \cdot \cdot, n)

$Values:

v_{i} = (v_{1}, v_{2}, \cdot \cdot \cdot, v_{i}, \cdot \cdot \cdot, v_{n})

$Weights:

w_{i} = (w_{1}, w_{2}, \cdot \cdot \cdot, w_{i}, \cdot \cdot \cdot, w_{n})

$Capacity of knapsack = M

If $x_{i}$ fraction of item is selected:

profit earned = (not provided in text)
weight added to knapsack = (not provided in text)

Total profit earned:

Objective Function

z = i = 1 \sum n v_{i} \cdot x_{i}

$Capacity Constraint

i = 1 \sum n v_{i} \cdot x_{i} \leq M

$where

x_{i} \in {0, 1}

Dynamic Programming Approach for 0/1 Knapsack

To solve zero-1 knapsack problem with dynamic programming approach, we need to divide the given problem into smaller sub-problems.

Starting from the smallest one, dynamic programming will increase the size of the problem.

Consider the i-th state, a general state in which DP is considering the first i items:

1, 2, 3, \cdot \cdot \cdot, i, \cdot \cdot \cdot, n

And the available knapsack capacity is $j$ , where j can take values from 0 to M.

Let

V_{ij}

be the optimal profit earned when we are considering the first i items and available knapsack capacity j.

Two Cases for the i-th Item

Case 1: We cannot include the $i^{t h}$ item into the knapsack

Example: (Not enough Available Space)

$j < w_{i}$
$j - w_{i} < 0$

Then:

V [i, j] = V [i - 1, j]

The previous best will continue.

Case 2: We do include the i-th item

Example:

$j \geq w_{i}$ or
$j - w_{i} \geq 0$

In this case, the i-th item will only be included if this inclusion maximizes the profit.

Thus we compare:

Value if i-th item not included:
$V [i, j] = V [i - 1, j]$
Value if i-th item included:
$V [i, j] = v_{i} + V [i - 1, j - w_{i}]$

Recurrence Relation

V_{ij} = ⎩ ⎨ ⎧ V_{i - 1, j} max (V_{i - 1, j}, v_{i} + V_{i - 1, j - w_{i}}) if j < w_{i} otherwise

Initial Condition

$V [i, 0] = 0 \forall$ (forall)
$V [0, j] = 0 \forall$ (farall)

Because:

When capacity = 0 → profit = 0 (for all items)
When items = 0 → profit = 0 (for all capacities)

Maximum Profit Definition

$V [n, m]$ is the maximum profit earned when we consider all the items from 1 to n and the maximum knapsack capacity M.

Our objective is to find:

V [n, m]

which represents the maximum profit.

Time Complexity

The complexity of this algorithm depends on the solution table of size:

(n + 1) \times (m + 1)

Thus, the time complexity of the dynamic programming-based 0/1 knapsack algorithm is:

O (nm)

Solution of 0/1 knapsack problem using DPA

Item $i$	Weight $(w_{i})$	Value $(V_{i})$
1	1	250
2	2	650
3	3	290

Here:

$n = 3, m = 4$

let $V [i, j]$ be the maximum profit earned when we consider the first i items, and j is the available knapsack capacity

DP Table (0/1 Knapsack)

Final DP Table

i \ j	1	2	3	4
0	0	0	0	0
1	250	250	250	250
2	250	650	900	900
3	250	650	900	*900*

Formula

$V [i, j] = max (V [i - 1] [j], v_{i} + V [i - 1] [j - w_{i}])$

teration i = 1 (Item 1: weight = 1, value = 250)

For j = 1

$V [1, 1] = max (V [0, 1], 250 + V [0, 1 - 1])$ $V [1, 1] = max (0, 250 + 0) = 250$ $

For j = 2

$V [1, 2] = max (V [0, 2], 250 + V [0, 2 - 1])$ $V [1, 2] = max (0, 250 + 0) = 250$ $

For j = 3

$V [1, 3] = max (V [0, 3], 250 + V [0, 3 - 1])$ $V [1, 3] = max (0, 250 + 0) = 250$ $

For j = 4

$V [1, 4] = max (V [0, 4], 250 + V [0, 4 - 1])$ $V [1, 4] = max (0, 250 + 0) = 250$ $

teration i = 2 (Item 2: weight = 2, value = 650)

For j = 1

Item weight $w_{2} = 2$ > capacity 1 → cannot include.

$V [2, 1] = V [1, 1] = 250$

For j = 2

$V [2, 2] = max (V [1, 2], 650 + V [1, 2 - 2])$ $V [2, 2] = max (250, 650 + 0) = 650$

For j = 3

$V [2, 3] = max (V [1, 3], 650 + V [1, 3 - 2])$ $V [2, 3] = max (250, 650 + 250) = 900$

For j = 4

$V [2, 4] = max (V [1, 4], 650 + V [1, 4 - 2])$

$V [2, 4] = max (250, 650 + 250) = 900$

Iteration i = 3 (Item 3: weight = 3, value = 290)

For j = 1

Weight 3 > capacity 1 → cannot include.

$V [3, 1] = V [2, 1] = 250$

For j = 2

Weight 3 > capacity 2 → cannot include.

$V [3, 2] = V [2, 2] = 650$

For j = 3

$V [3, 3] = max (900, 290 + 0) = 900$

For j = 4

$V [3, 4] = max (V [2, 4], 290 + V [2, 4 - 3])$

$V [3, 4] = max (900, 290 + 250) = 900$

Final Maximum Profit

V [3, 4] = 900

Your Assignment

Item $i$	Weight $(w_{i})$	Value $(V_{i})$
1	2	100
2	3	250
3	1	120
4	5	160

Where: Capacity $(M) = 6$

Dynamic Programming & 0/1 Knapsack

Dynamic Programming & 0/1 Knapsack

Applications of Dynamic Programming Approach

0/1 Knapsack Problem

Objective Function

Dynamic Programming Approach for 0/1 Knapsack

Two Cases for the i-th Item

Case 1: We cannot include the ith item into the knapsack

Case 2: We do include the i-th item

Recurrence Relation

Initial Condition

Maximum Profit Definition

Time Complexity

Solution of 0/1 knapsack problem using DPA

DP Table (0/1 Knapsack)

Formula

teration i = 1 (Item 1: weight = 1, value = 250)

For j = 1

For j = 2

For j = 3

For j = 4

teration i = 2 (Item 2: weight = 2, value = 650)

For j = 1

For j = 2

For j = 3

For j = 4

Iteration i = 3 (Item 3: weight = 3, value = 290)

For j = 1

For j = 2

For j = 3

For j = 4

Final Maximum Profit

Your Assignment

Case 1: We cannot include the $i^{t h}$ item into the knapsack