Given n objects and a “knapsack”

Item i weighs w_i > 0 kilograms and has value v_i > 0

Alternative: jobs require w _i time

Knapsack has capacity of W kilograms

Alternative: W is time interval that resource is available

Goal: Fill in the knapsack so as to maximize the total value.

False Start:

OPT(i) = max profit subset of items 1,…, i

Case 1: OPT does not select item i:

OPT selects best of { 1, 2, …, i-1 }

Case 2: OPT selects item i

Accepting item i does not immediately imply that we will have to reject other items: It implies that there are no known conflicts

Without knowing what other items were selected before i, we don't even know if we have enough room for i

Better solution