Scribd
Upload
52 views13 pages

10 Dynamic Programming - Knapsack

This document discusses the 0/1 knapsack problem and its solution using dynamic programming. It provides the mathematical formulation of the 0/1 knapsack problem, describes the algorithm to solve it using dynamic programming, and includes a numerical example.

Uploaded by

ctxxfx5ykz
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
52 views13 pages

10 Dynamic Programming - Knapsack

This document discusses the 0/1 knapsack problem and its solution using dynamic programming. It provides the mathematical formulation of the 0/1 knapsack problem, describes the algorithm to solve it using dynamic programming, and includes a numerical example.

Uploaded by

ctxxfx5ykz
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
You are on page 1/ 13

Design and Analysis of Algorithms

(Dynamic Programming-0/1 Knapsack)

Dr. D. P. Acharjya
Professor, SCOPE
2/7/2024 Dr. D. P. Acharjya 1
Dynamic Programming
 Dynamic programming typically applies to
optimization problems in which a set of choices
must be made in order to arrive at an optimal
solution.
 Characterize the structure of an optimal solution.
 Formulate the solution recursively.
 Computation is to be carried out in bottom up fashion.
 Optimal solution is constructed from computed
information.

2/7/2024 Dr. D. P. Acharjya 2


0/1 Knapsack Problem
 Given that a knapsack of capacity m. Suppose
that there are n-objects. Assume that the object
i has a weight wi. If a fraction xi of object i is
placed into the knapsack, the profit is xipi.

 The main objective of knapsack problem is to


obtain a filling of the knapsack that maximizes
the total profit.

2/7/2024 Dr. D. P. Acharjya 3


Mathematical Formulation

 Equation 1 is objective function


 Equation 2 is a constraint condition
 It is a 0 / 1 knapsack problem.
2/7/2024 Dr. D. P. Acharjya 4
 The set which satisfies equations (2)
and (3) is known as feasible solution.
 The feasible solution which maximizes the
objective function (1) is known as optimal
solution.
 Since it is a profit maximization problem,
objects having more profit in respect to
weights must be considered initially.

2/7/2024 Dr. D. P. Acharjya 5


2/7/2024 Dr. D. P. Acharjya 6
2/7/2024 Dr. D. P. Acharjya 7
0/1 Knapsack Algorithm

2/7/2024 Dr. D. P. Acharjya 8


2/7/2024 Dr. D. P. Acharjya 9
2/7/2024 Dr. D. P. Acharjya 10
Numerical Illustration
 Consider the knapsack of size 6, with
(w1,w2,w3)=(2,3,4) and (p1,p2,p3)=(1,2,5)

2/7/2024 Dr. D. P. Acharjya 11


2/7/2024 Dr. D. P. Acharjya 12
2/7/2024 Dr. D. P. Acharjya 13

You might also like