Announcements
Announcements
• Homework 5 Due on Friday
• Homework 4 Solutions online
Last Time
• Dynamic Programs
– Find family of related subproblems
– Find recurrence relation solving one subproblem
in terms of simpler ones
– Tabulate and solve all subproblems
Notes about DP
• General Proof of Correctness Outline:
– Prove by induction that each table entry is filled
out correctly
– Use base-case and recursion
• Runtime of DP:
– Usually
[Number of subproblems]x[Time per subproblem]
More Notes about DP
• Finding Recursion
– Often look at first or last choice and see what
things look like without that choice
• Key point: Picking right subproblem
– Enough information stored to allow recursion
– Not too many
Today
• Knapsack
Problem: Knapsack
You are a burglar and are in the process of
robbing a home. You have found several
valuable items, but the sack you brought can
only hold so much weight, what is the best
combination of items to steal?
Alternative formulations:
• Packing for a trip
• Deciding what modules to put on a spacecraft
Specification
You have an available list of items. Each has a
(non-negative integer) weight, and value. Your
sack also has a capacity.
The goal is to find the collection of items so that:
1. The total weight of all the items is less than
the capacity
2. Subject to 1, the total value is as large as
possible.
Variations
There are two slight variations of this problem:
1. Each item can be taken as many times as you
want.
2. Each item can be taken at most once.
Question: Knapsack
Given the knapsack problem below (only one
copy of each item), what is the best set of
items to take?
Capacity:
6
BD
Weight = 6
Value = $9
Greedy Algorithms Don’t Work
Most valuable item Biggest Value/Weight
Capacity = 6
Greedy:
A = $10
Optimal:
B+C = $18
Greedy:
A = $5
Optimal:
B+C = $6
Subproblems (multiple copies version)
What are our subproblems?
• If you make one choice of an item to go into the bag, what is
left?
– Remaining items must have total weight at most Capacity –
Weight of item
– Total value equals
Value of item + Value of other items
– Want to maximize value of other items subject to their
weight not exceeding Capacity-Weight of chosen item
• Subproblem: BestValue(Capacity’).
Recursion
What is BestValue(C)?
Possibilities:
• No items in bag
– Value = 0
• Item i in bag
– Value = BestValue(C-weight(i)) + value(i)
Recursion: BestValue(C) =
Max(0, Maxwt(i) ≤C (val(i)+BestValue(C-wt(i)))
Algorithm
Knapsack(Wt,Val,Cap)
Create Array T[0…Cap]
For C = 0 to Cap
T[C] ← 0
For items i with Wt(i) ≤ C
If T[C] < Val(i)+T[C-Wt(i)] T[C] ← Val(i)+T[C-Wt(i)] Return T[Cap] O(Cap) Subproblems O(#items) time/subproblem Runtime: O([Cap] [#Items]) Example Capacity: 6 BestValue C 0 $0 1 2 3 4 5 6 $1 $4 $5 $8 $9 $12 $0 or $1+$0 $0 or $1+$1 or $4+$0 $0 or $1+$4 or $4+$1 or $3+$0 $0 or $1+$5 or $4+$4 or $3+$1 or $5+$0 $0 or $1+$8 or $4+$5 or $3+$4 or $5+$1 $0 or $1+$9 or $4+$8 or $3+$5 or $5+$4 B B B B+B+B = $12 Non-Repeating Items Let’s try this with non-repeating items. • If we put some item in the sack: – Other items must have total weight at most Capacity – Weight(chosen item) – Total value is value(other items)+value(chosen item) – Chosen item cannot be picked again. • Recursion needs to keep track of remaining capacity and the item that cannot be used. Attempt 1 Let’s make subproblem BestValue≠i(Cap) – the best value achievable without using item i that doesn’t go over capacity. Can we make a recursion with this? No! After using item j, the remaining items cannot include i or j. Attempt 2 BestValue excluding 2 items? No… recursive calls would need to exclude a 3rd and so on. BestValueS(Cap) – best value achievable using only items from S with total weight at most Cap. BVS(Cap) = maxi∈S(Val(i) + BVS-i(Cap-Wt(i))) [or 0] We have a recursion! Unfortunately, this is too slow. The number of subproblems is more than 2#items. Attempt 3 • Need to try something different. • Imagine items coming along a conveyor belt. You decide one at a time whether or add to your sac. • Last item: either add or don’t. – Add: BestValue≤n-1(Cap-Wt(n)) + Val(n) – Don’t add: BestValue≤n-1(Cap) • We only need subproblems of the form BestValue≤k(Cap) . Recursion BestValue≤k(Cap) = Highest total value of items with total weight at most Cap using only items from the first k. Base Case: BestValue≤0(C) = 0 Recursion: BestValue≤k(C) is the maximum of 1. BestValue≤k-1(C) 2. BestValue≤k-1(C- Wt(k))+Val(k) [where this is only used if Wt(k) ≤ Cap] Example Capacity: 6 ∅ A AB ABC ABCD Cap $0 0 1 2 3 4 5 6 $0 $0 $0 $0 $0 $0 $0 $0 $0 $0 $1 $1 $1 $1 $1 $1 $1 $4 $5 $5 $5 $5 $1 $4 $5 $5 $7 $8 $1 $4 $5 $5 $7 $9 D B B+D = $9 Runtime • Number of Subproblems: O([Cap] [#items]) • Time per subproblem O(1) – Only need to compare two options. • Final runtime O([Cap][#items]).