Class Notes (809,569)
United States (313,690)
Lecture

# Lecture23 - Dynamic Programming.pdf

2 Pages
72 Views

School
University of California - Berkeley
Department
Computer Science
Course
COMPSCI 170
Professor
Satish Rao
Semester
Fall

Description
CS170: Efﬁcient Algorithms and Intractable Problems Lecture 23 October 25, 2013 Lecturer: Satish Rao Scribe: Amy Boone 1 Knapsack without Repetition Given: weight:W, items: (v1;w 1;(v 2w )2:::;(v nw )n Find: highest value subset of items of weight ▯ W (total capacity of the knapsack) Best knapsack using ﬁrst i items also depends on how much space is left K(w;i) = ”best weight w knapsack with subset of ﬁrst i items” K(w;i) = maxfK(w ▯ w ;i ▯ i) + v ;K(w;0 ▯ 1)g K(0;0) = 0 i Time: nW entries, many subsets! (2 ) 1.1 DAG View With repetition: K(w) = max (Kiw ▯ w ) + 0 ) i ▯(w) nodes and O(nW) edges Without repitition: K(w;
More Less

Related notes for COMPSCI 170

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.