0/1 KNAPSACK PROBLEM
GROUP-16
DESIGN & ANALYSIS OF ALGORITHM
NAME: Dibyanshu Shekhar Dey
ROLL: 10201619054
GROUP MEMBER
KAUSHEKI ROY (10200320052)
MD SOHAIL (10200320053)
SHAYAK MAJUMDER (10200719033)
ANKIT AGARWAL (10201619014)
DIBYANSHU SHEKHAR DEY (10201619054)
PROBLEM DESCRIPTION
In the 0-1 knapsack problem, we are given a set of items each with a weight and
value and we need to determine the number of each item to include in a collection
so that the total weight is less than or equal to a given limit and the total value is as
large as possible.
Since this is a 0 1 Knapsack problem algorithm, we can either take an entire
item or reject it completely.
We can not break an item and fill the knapsack.
WHAT IS DYNAMIC PROGRAMMING?
Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it
down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem
depends upon the optimal solution to its subproblems.
Dynamic Programming Methods
1. Top-down with Memoization
2. Bottom-up with Tabulation
1. Top-down with 2. Bottom-up with
Memoization Tabulation
Tabulation is the opposite of the
In this approach, we try to solve
top-down approach and avoids
the bigger problem by recursively
recursion. The bottom-up approach
finding the solution to smaller
consists in first looking at the "smaller"
[Link] technique of
subproblems, and then solve the larger
storing the results of already
subproblems using the solution to the
solved subproblems is called
smaller problems by filling up an
Memoization.
ndimensional table.
Example: The maximum weight the knapsack can hold is W is 11. There are five items to choose from.
Their weights and values are presented in the following table:
V [i, j] = max {V [i - 1, j], vi + V [i - 1, j -wi]
or V[i – 1][j]
w2]
= max {V [1, 3], 6 + V [1, 3- 2]
= max {1, 6+ 1}
=7
V [3, 7] = max {V [3 - 1, 7], v3 + V [3 - 1, 7 - w3]
= max {V [2, 7], 18 + V [2, 7 - 5]}
= max {7, 18 + 6}
= 24
{
int i, w;
int K[n + 1][W + 1];
for(i = 0; i <= n; i++)
{
for(w = 0; w <= W; w++)
{
if (i == 0 || w == 0) K[i][w] = 0; else if (wt[i - 1] <= w) K[i][w] = max(val[i -
1] +
K[i - 1][w - wt[i - 1]],
K[i - 1][w]); else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
OUTPUT
COMPLEXITY ANALYSIS:
Time Complexity: O(N*W)
where ‘N’ is the number of weight elements and ‘W’ is capacity. As for every weight
element we traverse through all weight capacities 1<=w<=W.
Each entry of the table requires constant time θ(1) for its
It takes θ(nw) time to fill (n+1)(w+1) table entries.
Auxiliary Space: O(N*W)
The use of 2-D array of size ‘N*W’.
OPTIMIZATION TECHNIQUE
We are suggesting bottom-up approach as optimization technique
Bottom-up approach is easy to debug.
Bottom-up approach is difficult to implement but it is usually faster. Bottom up implementations have a better
performance, and top down approach often results in worse complexities.
We can in certain cases avoid recursion by using iterative bottom up dynamic programming,
and using bottom up approach, using certain specific data structures we can improve
performance and we can get a better and optimal complexity.
So performance wise top-down is generally worse in case of complexity.
DISCUSSION
Dynamic programming is a useful technique of solving certain kind
of problems When the solution can be recursively described in
terms of partial solutions, we can store these partial solutions and
re-use them as necessary
(memoization)
Running time of dynamic programming algorithm vs. naïve
algorithm: » 0-1 Knapsack problem: O(W*n) vs. O(2 ^n )
BIBLIOGRAPHY
[Link]
[Link]
[Link]
[Link] and analysis of algorithms 01
[Link]
THANK YOU