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

OPT(i, w) = max profit subset of items 1,…, i with weight limit w

Case 1: OPT does not select item i:

OPT selects best of { 1, 2, …, i-1 } using weight limit w

Case 2: OPT selects item i:

new weight limit = w – w_i

OPT selects best of { 1, 2, …, i–1 } using new weight limit, w – w_i

So, OPT(i,w) is:

0 if i =0

OPT(i-1,w) if w_i > w

max{OPT(i-1,w), v_i + OPT(i-1,w-w_i)} otherwise

Input: N, w<sub>1M/sub>,…,w_N, v₁,…,v_N

for w = 0 to W: O(W) time

M[0, w] = 0

for i = 1 to N: –> For all items

for w = 1 to W: –> For all possible weights( So O(NW) time

if w_i > w : –> item's weight is more than available

M[i, w] = M[i-1, w]

else:

M[i, w] = max{ M[i-1, w], vi + M[i-1, w-wi] }

return M[n,W]

Algorithm Analysis

• The algorithm takes Θ(nW) time to compute the optimal value of the problem.
• Given a table M of the optimal values of the subproblems, the optimal set S can be found in O(n) time.
• Thus the Knapsack Problem can be solved in O(nW) time.

I give this section an 8/10.