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 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=\sum_{i=1}^{n}v_{i}\cdot x_{i}

$Capacity Constraint

\sum_{i=1}^{n}v_{i}\cdot x_{i}\le 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,\mathbf{i},\cdot\cdot\cdot,n

And the available knapsack capacity is , 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 item into the knapsack

Example: (Not enough Available Space)

Then:

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

The previous best will continue.

Case 2: We do include the i-th item

Example:

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}=\begin{cases}V_{i-1,\,j} & \text{if }j<w_{i}\\[6 pt] \max\left(V_{i-1,\,j},\;v_{i}+V_{i-1,\,j-w_{i}}\right) & \text{otherwise}\end{cases}

Initial Condition

(forall)
(farall)

Because:

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

Maximum Profit Definition

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	Weight	Value
1	1	250
2	2	650
3	3	290

Here:

let 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

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

Item weight > capacity 1 → cannot include.

For j = 2

For j = 3

For j = 4

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

For j = 1

Weight 3 > capacity 1 → cannot include.

For j = 2

Weight 3 > capacity 2 → cannot include.

For j = 3

For j = 4

Final Maximum Profit

V[3,4]=\boxed{900}

Your Assignment

Item	Weight	Value
1	2	100
2	3	250
3	1	120
4	5	160

Where: Capacity