Data Structures and Algorithms with Object-Oriented Design Patterns in C#
next up previous contents index

Example-0/1 Knapsack Problem Again

Consider again the 0/1 knapsack problem described in Section gif. We are given a set of n items from which we are to select some number of items to be carried in a knapsack. The solution to the problem has the form tex2html_wrap_inline67636, where tex2html_wrap_inline67478 is one if the tex2html_wrap_inline57621 item is placed in the knapsack and zero otherwise. Each item has both a weight, tex2html_wrap_inline67468, and a profit, tex2html_wrap_inline57649. The goal is to maximize the total profit,

displaymath67630

subject to the knapsack capacity constraint

displaymath67463

A partial solution to the problem is one in which only the first k items have been considered. That is, the solution has the form tex2html_wrap_inline67648, where tex2html_wrap_inline67650. The partial solution tex2html_wrap_inline67652 is feasible if and only if

  equation32619

Clearly if tex2html_wrap_inline67652 is infeasible, then every possible complete solution containing tex2html_wrap_inline67652 is also infeasible.

If tex2html_wrap_inline67652 is feasible, the total profit of any solution containing tex2html_wrap_inline67652 is bounded by

  equation32624

That is, the bound is equal the actual profit accrued from the k items already considered plus the sum of the profits of the remaining items.

Clearly, the 0/1 knapsack problem can be solved using a backtracking algorithm. Furthermore, by using Equations gif and gif a branch-and-bound solver can potentially prune the solution space, thereby arriving at the solution more quickly.

For example, consider the 0/1 knapsack problem with n=6 items given in Table gif. There are tex2html_wrap_inline67666 possible solutions and the solution space contains tex2html_wrap_inline67668 nodes. The simple DepthFirstSolver given in Program gif visits all 127 nodes and generates all 64 solutions because it does a complete traversal of the solution tree. The BreadthFirstSolver of Program gif behaves similarly. On the other hand, the DepthFirstBranchAndBoundSolver shown in Program gif visits only 67 nodes and generates only 27 complete solutions. In this case, the branch-and-bound technique prunes almost half the nodes from the solution space!


next up previous contents index

Bruno Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.