Scribd
Upload
49 views17 pages

AOA Dynamic Programming 01kanpsack

The document provides an overview of the 0/1 Knapsack Problem, detailing its characteristics, dynamic programming approach, and steps to solve it. It includes a method for filling a table to determine the maximum value that can be placed in the knapsack and identifies the items to include for maximum profit. Additionally, it discusses the time complexity of the algorithm and references key literature on algorithms.

Uploaded by

aryavinodk83
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
49 views17 pages

AOA Dynamic Programming 01kanpsack

The document provides an overview of the 0/1 Knapsack Problem, detailing its characteristics, dynamic programming approach, and steps to solve it. It includes a method for filling a table to determine the maximum value that can be placed in the knapsack and identifies the items to include for maximum profit. Additionally, it discusses the time complexity of the algorithm and references key literature on algorithms.

Uploaded by

aryavinodk83
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Analysis of Algorithms

CE – SE –SEM IV
Suneha Raut
SIES Graduate School of Technology

1
Overview
• General Method, Backtracking

• N-queen problem

• Sum of subsets

• Branch and Bound: Travelling Salesperson Problem,

• Graph coloring

• 15 Puzzle problem

3
4.6 0/1 KNAPSACK

4
5
0/1 Knapsack Problem-

In 0/1 Knapsack Problem,

• As the name suggests, items are indivisible here.


• We can not take the fraction of any item.
• We have to either take an item completely or leave it
completely.
• It is solved using dynamic programming approach.

6
• Consider-

• Knapsack weight capacity = w


• Number of items each having some weight and value = n

7
Step-01:
• Draw a table say ‘T’ with (n+1) number of rows and (w+1)
number of columns.
• Fill all the boxes of 0th row and 0th column with zeroes as
shown-

8
Step-02:
• Start filling the table row wise top to bottom from left to right.
• Use the following formula-
• T (i , j) = max { T ( i-1 , j ) , value i + T( i-1 , j – weight i ) }
• Here, T(i , j) = maximum value of the selected items if we can
take items 1 to i and have weight restrictions of j.
• This step leads to completely filling the table.
• Then, value of the last box represents the maximum possible
value that can be put into the knapsack.

9
Step-03:
• To identify the items that must be put into the knapsack to
obtain that maximum profit,

• Consider the last column of the table.


• Start scanning the entries from bottom to top.
• On encountering an entry whose value is not same as the value
stored in the entry immediately above it, mark the row label of
that entry.
• After all the entries are scanned, the marked labels represent
the items that must be put into the knapsack.

10
• Time Complexity-
• Each entry of the table requires constant time θ(1) for its
computation.
• It takes θ(nw) time to fill (n+1)(w+1) table entries.
• It takes θ(n) time for tracing the solution since tracing process
traces the n rows.
• Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem
using dynamic programming.

11
Example

12
Answer

13
14
• Write the algorithm for 0/1 knapsack using dynamic
programming. Also solve the following instance where M=21,
n=4, (p1, p2, p3, p4) =(2,5,8,1), (w1,w2,w3,w4)=(10,15,6,9)
• May 2024

15
References
• books:
• 1 T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, “Introduction to algorithms”, 2nd
Edition, PHI Publication 2005.
• Ellis Horowitz, Sartaj Sahni, S. Rajsekaran. “Fundamentals of computer algorithms”
University Press.

16
•THANK YOU

17

You might also like