This is an old revision of the document!
Table of Contents
6.4 Subset Sums and Knapsacks: Adding a Variable
The Problem
Given n objects and a “knapsack”
Item i weighs wi > 0 kilograms and has value vi > 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.
Designing the Algorithm
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 – wi
OPT selects best of { 1, 2, …, i–1 } using new weight limit, w – wi
SO, OPT(i,w) is:
0 if i =0
OPT(i-1,w) if wi > w
max{OPT(i-1,w), vi + OPT(i-1,w-wi)} otherwise
