[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

Here's a  program that demonstrates "Exhaustive" and "Branch and Bound" search methods for finding the
best solution for "Knapsack" problems.  It was adapted with author's kind permission from the book "Ready-to-Run Delphi 3.0 Algorithms", Rod Stephens, Wiley Computer Publishing.

Background & Techniques

The Knapsack Problem requires that we figuratively fill a knapsack by selecting from a set of items whose
weight (or other "cost" measurement) and value (or "profit") are known. The objective is to maximize the value (profit) of the items in the sack without exceeding a predefined weight (cost) limit.

The "Exhaustive Search" method tries every combination of including or excluding items to find the valid set with the largest value .  For N items, there are 2^N  combinations because for each item there are 2 choices; include the item or exclude this item.  Actually, we'll call it  2^N - 1 because the empty solution is not really a solution.  The possible combinations can be represented as a "binary tree" with the each path from the starting "root" to the terminal "leaf" representing a unique set of items. These paths or combinations can also be represented by the binary notation of numbers from 0 to 2^N-1 . So, for example with 3 items, 8 combinations, the path including items 1 and 2, but excluding item 3 could be represented by the number 6 (binary 110).  Exhaustive search times for current PCs soon become unreasonable when we have more than  30 items to choose from.  The 30 item  decision tree has about  a billion possible paths.   My Dell Studio 17 Laptop checks about 50 million paths per second so takes 20 seconds to solve the 30 item case.  Each additional item will double the number of paths to check and  double the time to solve by exhaustive search.

"Branch and bound" is an algorithm that significantly reduces the number of combinations to be checked. It "prunes" the search tree" by aborting search paths when they could not not possibly improve the best solution found to date.  The program  allows viewing the process step by step here is a simple example:

Assume we have three items  with [Cost, Profit] values of [30,8], [25,4]. [40,3] and maximum cost of 50.  Well  start the process down the right side of the tree by including item #1.  The 4 paths including item #1 are {#1}, {#1,#2}, {#1,#3} and {#1,#2,#3}.  Adding  either item #2 or #3 would exceed our cost limit so out first "best" solution is just item #1 with profit of 8.    Now we have 3 paths left to check, {#2}, {#2,#3} and  {#3}.   But before doing that we'll do the Branch and Bound trick of checking the maximum profit if item #1 is excluded.  That number is the maximum profit if all items could be included (15) minus the profit represented by the solution so far (8)  So the maximum profit from any path on the left side the tree is 7  (15 - 8 = 7). That number is less than our best profit so far (8), so no need to check any of those paths and we are done!  A example with 4 items might  be more convincing, but hard to explain.  Run Branch and Bound on a small case with the "Visualize steps" box checked for further study.

The Demo page is self explanatory. You can enter you own data or generate random cases and solve them using either algorithm. The "Start" button will turn into a "Stop" button during solving in case a problem is running longer than you care to wait. For instructional purposes, you can see click the checkbox at the top right of the form to follow the steps taken by Branch and Bound algorithm as it finds the best solution. there are "Save and "Load" buttons in case you want to preserve a case for future reference or for reporting a bug to me,

I want to thank author Rod Stephens for permission to use his program as the basis for this one and for the book that helped me understand how it works.   The book is   "Ready-to-Run Delphi 3.0 Algorithms", Rod Stephens, Wiley Computer Publishing.  It was an experiment by Rod into Delphi as a second (or third or fourth) language and he has since concentrated on Visual Basic and C#.  That's OK, I have investigated VB,  (the best "other" language for beginners IMO), but reverted to Delphi.  Experienced programmers typically have a "native" language as their language of choice.  Rod runs websites  VB Helper (http://www.vb-helper.com) and C# Helper (http://www.csharphelper.com) where we might find items of interest to Delphians.   

Running/Exploring the Program 

Suggestions for Further Explorations

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.