Example-0/1 Knapsack Problem Again

Consider again the 0/1 knapsack problem described in Section . 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 , where is one if the item is placed in the knapsack and zero otherwise. Each item has both a weight, , and a profit, . The goal is to maximize the total profit,

subject to the knapsack capacity constraint

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

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

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

I.e., 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  and  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 . There are possible solutions and the solution space contains nodes. The simple DepthFirstSolver given in Program  visits all 127 nodes and generates all 64 solutions because it does a complete traversal of the solution tree. The BreadthFirstSolver of Program  behaves similarly. On the other hand, the DepthFirstBranchAndBoundSolver shown in Program  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!

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