Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 15
Consider any instance of the 0/1 knapsack problem.
Let O
be the set of objects packed into the knapsack
in some optimal solution and
let PO be the profit earned by this solution.
Let PB be the profit earned by the
bounded-performance solution.
If O has fewer than two objects,
the bounded-performance solution
must also be optimal as the bounded-performance agorithm
tries all single object packings.
So, assume that O has more than one object.
Let i denote the object in O
that has maximum profit.
The profit of any other object j in O
is <= PO/2 (otherwise, pi +
pj > PO).
Consider the time the bounded-performance heuristic starts
by putting object i into the knapsack.
Let B denote the objects
that are packed into the knapsack at this time.
Let s be the object with highest profit density
that is in O but not
in B. If there is no such object, B
must also be an optimal solution and the error bound is established.
Let CB be the capacity used by objects other than
i packed into the knapsack before object s
is excluded by the greedy method. In both O and
B this capacity is packed by the same objects and so earns
the same profit. When object s is excluded by the
greedy packing, the
available capacity is less than ws
and is filled in the optimal solution by objects with profit density
no more than
ps/ws. So the additional profit
generated by O is less than
ps, which is no more than
PO/2.
Consequently, PO - PB < PO/2 and
(PO - PB)/PO < 1/2.