Dynamic
Programming
M. Ashraf Iqbal
http://www.istockphoto.com/stock-illustration-12665058-armed-robbery.php
Monday, 25 February 13
The Knapsack
Problem
Monday, 25 February 13
The 0/1 Knapsack
Problem
The 0-1 knapsack problem: Either put
an item once in the knapsack or ignore
it so as to maximize total profit while
keeping the weight inside the
knapsack within its capacity.
Alternately we may like to ignore
profits and try to maximize the weight
in the knapsack such that it does not
exceed its capacity. This is quite
Monday, 25 February 13
You can
Cut an Item
The Fractional knapsack problem:
Either put an item or its fraction in the
knapsack or ignore it so as to maximize total
profit while keeping the weight inside the
knapsack exactly equal to its capacity.
Monday, 25 February 13
Un-Bounded 0/1
Knapsack
The unbounded knapsack problem assumes that
we have an unlimited supply of each weight. We
intend to fill the knapsack as far as possible while
keeping the total number of weights minimum (also
known as the Change Problem). We can also
maximize profit provided profit for each weight is
also given.
Monday, 25 February 13
Un-
http://www.fotosearch.com/BLD007/jp2005_0002521/
Monday, 25 February 13
Another Knapsack Problem
The bounded 0/1 knapsack
problem restricts the number
of each item to a fixed
maximum value.
Monday, 25 February 13
Objectives
1. We may like to maximize the
number
of weights to be placed in the
knapsack such that the total
weight remains within the
knapsack capacity in a 0/1
scenario.
1. We may like to maximize the
profit provided the profit of each
weight is the same.
2. We may like to maximize profit
provided the weight of each item
is the same.
Monday, 25 February 13
How Many Knapsack
Problems?
What Strategies should be used?
Greedy?
Dynamic Programming?
Brute Force look at all options?
What is Greedy
What is Dynamic Programming
What is the relationship between Greedy,
Dynamic Programming, & Brute force
Strategies?
Monday, 25 February 13
Which Strategy is better?
Brute Force is expensive but?
Dynamic Programming is intelligent
but?
Greedy is FAST but?
Monday, 25 February 13
Which Strategy?
Brute Force can solve every thing?
Dynamic Programming can solve some
thing?
How about Greedy?
Monday, 25 February 13
Start with the
Change Problem?
Monday, 25 February 13
Start with the Change
Problem?
Monday, 25 February 13
Monday, 25 February 13
The Recursion Tree
Monday, 25 February 13
Recursive Formulation?
Recursion Tree?
Monday, 25 February 13
The Change Problem transforms into a Graph
Problem?
Find a Change = Find a Path?
Monday, 25 February 13
Monday, 25 February 13
Find a Change = Find a Shortest
Path?
Monday, 25 February 13
Where is Brute Force, DP, & Greedy?
Monday, 25 February 13
Do it by Brute Force?
Monday, 25 February 13
Do it by Dynamic
Programming?
Monday, 25 February 13
Do it by Greedy?
Monday, 25 February 13
The Change Problem?
Brute Force provides an
Optimal answer?
Dynamic Programming
provides an Optimal
answer?
Greedy strategy provides
an Optimal answer?
Monday, 25 February 13
Profits & Weights in a
Knapsack?
How to start now?
Monday, 25 February 13
Profits & Weights in a
Knapsack?
Monday, 25 February 13
Monday, 25 February 13
Where is Brute Force, DP, &
Greedy?
Monday, 25 February 13
Do it by Brute Force?
Monday, 25 February 13
Greedy: The Graph collapses?
Monday, 25 February 13
Dynamic Programming: It
Collapses? But?
Monday, 25 February 13
Do it by Dynamic
Programming?
Monday, 25 February 13
The Change
Problem
Do it by Dynamic
Programming?
Monday, 25 February 13
The Change
Problem
Do it by Dynamic
Programming?
Monday, 25 February 13
The Change
Problem
Do it by Dynamic
Programming?
Monday, 25 February 13
Maximizing
Profit
Do it by Dynamic
Programming?
Monday, 25 February 13
Maximizing
Profit
Do it by Dynamic
Programming?
Monday, 25 February 13
Time complexity calculations?
Monday, 25 February 13
The Knapsack Problem?
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
The Knapsack Problem?
The above diagram shows a recursive
implementation of which recursive equation?
Discuss briefly. We have not yet gone into
dynamic programming.
How can you find (from the above diagram)
the combination of weights that exactly fits
the knap sack of given capacity equal to 11.
Discuss briefly.
The answer to the above part requires a
cute reduction of this problem into a
graph problem? What is that graph problem?
Monday, 25 February 13
A New Recursive Formulation?
P(5,11) = P(4,5) + 6
= P(4,6) +
5
= P(4,7) +
4
= P(4,8) +
max
3
= P(4,9) +
2
Monday, 25 February 13
A Last Year Mistake??
Monday, 25 February 13
A Last Year Mistake??
Monday, 25 February 13
Monday, 25 February 13
Last Year Class: Hisaan to the
Monday, 25 February 13
Last Year Class: Hisaan to the
Monday, 25 February 13
Alternate Recursive
Monday, 25 February 13
Old Recursive Formulation?
Monday, 25 February 13
The Knapsack Problem
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Another Knapsack Problem
Problem: We have k lists of
integers and a knapsack of
capacity T. We need to select one
item from each list such as to
maximize the total weight in the
knapsack without overflowing it.
Here is recursive solution
Monday, 25 February 13
Monday, 25 February 13
Problem: We have k lists of integers
and a knapsack of capacity T. We need
to select one item from each list such
as to maximize the total profit in the
knapsack such that the weight in the
knapsack remains within its capacity.
Here is recursive solution unfolding
itself with some common sense.
Monday, 25 February 13
Monday, 25 February 13
Problem: We have
k lists of integers
and a knapsack
of capacity T. We
need to select
one item from
each list such as
to maximize the
total weight in
the knapsack
without
overflowing it.
Here is an
efficient dynamic
programming
solution.
Monday, 25 February 13
Monday, 25 February 13
The Knapsack Problem
We intend to maximize profit keeping the
total weight within the knapsack capacity.
Find a recursive equation corresponding
to this scenario. How will you implement
this recursive equation on the diagram
above?
How can you find (from the above
recursive diagram) the combination of
weights that maximizes total profit
keeping the total weight within knapsack
capacity? Discuss briefly.
How can you reduce this graph and thus
reduce the time complexity of this
Monday, 25 February 13
The Problem of Maximizing
Monday, 25 February 13
The Problem of Maximizing
Number of Elements in a single
Monday, 25 February 13
Monday, 25 February 13
The Activity Selection
Monday, 25 February 13
Activity Selection Problem?
Monday, 25 February 13
Monday, 25 February 13
Activity Selection Problem
Maximize Total Merit with Start time
and Finish time fixed for each activity?
Maximize Total Merit when only
Duration is fixed for each activity?
Maximize the Total Utilization of the
Hall?
Maximize the Total Number of
activities?
Monday, 25 February 13
Monday, 25 February 13
Activity Selection Problem?
Monday, 25 February 13
Maximize Merit
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Complexity of Graph
Construction
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
The Partitioning Problem
Problem: Given a fixed sequence of n
numbers, we wish to divide the sequence into
at most p partitions as fairly as possible (you
know the problem already). Assume that we
are given the following sequence (5, 1, 2, 3,
4) and assume that p =2.
Write down a general recursive formulation of
the linear partition problem. Find the optimal
answer by inspection for the specific problem
given above.
Draw the recursion tree similar to the one
drawn in Fig. 7(attached herewith). Remember
that in the present problem p=2. Highlight
Monday, 25 February 13
The Partitioning Problem
(5, 1, 2, 3, 4,
3)
Monday, 25 February 13
Monday, 25 February 13
Partition the sequence into 4
partitions
(5, 1, 2, 3, 4,
3)
Monday, 25 February 13
Partition the sequence
into 4 partitions
(5, 1, 2, 3, 4,
3)
Monday, 25 February 13
Partition the sequence
into 4 partitions
(5, 1, 2, 3, 4,
3)
Time Complexity?
Number of
Vertices
Number of Edges
Monday, 25 February 13
Partition the sequence into 4
(5, 1, 2, 3, 4,
partitions
3)
Monday, 25 February 13
Once again the Partitioning
Problem?
Monday, 25 February 13
The Same Problem but?
Monday, 25 February 13
Partition the sequence into 4
(5, 1, 2, 3, 4,
partitions
3)
Monday, 25 February 13
Add one more level but
Monday, 25 February 13
Add one more level but
Monday, 25 February 13
The Rod Partitioning
The size - price table
Cutting costs?
Monday, 25 February 13
The Rod Partitioning
1. No cutting
cost?
2. Uniform
cutting cost?
3. Non uniform
cutting cost
Monday, 25 February 13
The Rod Partitioning
The size - price
table
Monday, 25 February 13
The Rod
Partitionin
g Problem
The size - price
table
Monday, 25 February 13
The Rod
Partitionin
g Problem
The size - price
table
Monday, 25 February 13
The Rod Partitioning
Cutting Cost = 0
Maximum Price =
13
Monday, 25 February 13
The Rod Partitioning
The size - price
table
Monday, 25 February 13
The Rod
Partitioning
Monday, 25 February 13
Length & Price is
given put
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
How many vertices,
Monday, 25 February 13
Dynamic
Monday, 25 February 13
Dynamic
Monday, 25 February 13
Dynamic
Monday, 25 February 13
Dynamic
Total vertices and
Monday, 25 February 13
Dynamic
Programming
Monday, 25 February 13
Directed Acyclic Graph
Monday, 25 February 13
How about a fixed cutting
cost?
Monday, 25 February 13
Maximizing profits after subtracting
total cutting costs
Monday, 25 February 13
Maximizing profits after subtracting
total cutting costs
Monday, 25 February 13
Maximizing profits after subtracting
total cutting costs
Monday, 25 February 13
Maximizing profits after subtracting
total cutting costs
Monday, 25 February 13
Profits
after
cutting
Monday, 25 February 13
Total
Vertices?
Total Edges?
Time
Complexity?
Monday, 25 February 13
An alternate way of solving it?
Monday, 25 February 13
An alternate way
of solving it?
Monday, 25 February 13
Monday, 25 February 13
How the DAG will
change? In shape? In
edge weights?
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Once again the partitioning
problem
Given a fixed sequence of n positive
numbers how can we partition it in k
partitions such that the weight of the
heaviest partition is minimum.
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Once again the partitioning
problem?
Given a fixed sequence of n positive
numbers how can we partition it in k
partitions such that the weight of the
heaviest partition is minimum.
How about if k=n?
Monday, 25 February 13
Once again the partitioning
problem?
Given a fixed sequence of n positive
numbers how can we partition it in k
partitions such that the weight of the
heaviest partition is minimum.
How about if some numbers are
negative?
Monday, 25 February 13
Once again the partitioning
problem?
How about if some numbers are
negative?
What should be the value of k so as to
minimize the weight of the heaviest
partition?
The value of k could be just 1?
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Why can not be the DAG like this or
that?
Monday, 25 February 13
How the DAG
would look
like if some
edge weights
are negative
but k is fixed
from above?
Monday, 25 February 13
Monday, 25 February 13
Matrix Multiplication
Problem?
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
The Longest or shortest path
Monday, 25 February 13
The
Monday, 25 February 13
Longest Increasing sequence
What is this problem?
Monday, 25 February 13
Longest Increasing Sub What is this problem?
Monday, 25 February 13
Monday, 25 February 13
Monday, 25 February 13
