Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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_inline67353, where tex2html_wrap_inline67195 is one if the tex2html_wrap_inline57340 item is placed in the knapsack and zero otherwise. Each item has both a weight, tex2html_wrap_inline67185, and a profit, tex2html_wrap_inline57368. The goal is to maximize the total profit,

displaymath67347

subject to the knapsack capacity constraint

displaymath67180

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_inline67365, where tex2html_wrap_inline67367. The partial solution tex2html_wrap_inline67369 is feasible if and only if

  equation32371

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

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

  equation32376

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_inline67383 possible solutions and the solution space contains tex2html_wrap_inline67385 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 © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.