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:
The total weight of all the items is less than the capacity
Subject to 1, the total value is as large as possible.
Variations
There are two slight variations of this problem:
Each item can be taken as many times as you want.
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
BestValue≤k-1(C)
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]).