Home arrow Development Cycles arrow Page 4 - Branch and Bound Algorithm Technique

Branch and Bound Algorithm Technique

Branch and bound is another algorithm technique that we are going to present in our multi-part article series covering algorithm design patterns and techniques. B&B, as it is often abbreviated, is one of the most complex techniques and surely cannot be discussed in its entirety in a single article. Thus, we are going to focus on the so-called A* algorithm that is the most distinctive B&B graph search algorithm.

Author Info:
By: Barzan "Tony" Antal
Rating: 4 stars4 stars4 stars4 stars4 stars / 29
October 21, 2008
  1. · Branch and Bound Algorithm Technique
  2. · The Theory
  3. · The Theory, Continued
  4. · Conclusions of the Knapsack

print this article

Branch and Bound Algorithm Technique - Conclusions of the Knapsack
(Page 4 of 4 )

The Knapsack problem is a combinatorial optimization problem. You are given a set of items, each with its own cost and value, and you are to determine the number of each item that you should pack into the knapsack so that the total cost doesn't exceed the given limitation, but the total value is as high as possible. As you can see, this is a maximization problem; it is part of combinatorics and applied mathematics.

The value is the weight of the items, and their cost represents how much the item is worth. The knapsack can hold a specified amount of weight, and this limitation cannot be exceeded. In short, you want to maximize the storage capability of the knapsack by packing the most valuable items in it. Sometimes this problem is told in the form of a robbery. Obviously, the thief wants the best bang for his buck (his effort).

Let's say the weight of the items are W1, W2, ... Wk, ... Wn and their cost is C1, C2, ... Ck, ... Cn, respectively; the capacity of the knapsack is specified as K. Now we have the following mathematical formula to calculate the upper bound [UB]. Check it out!

Right after this point we can already present the pseudocode of the algorithm.

Procedure knapsack:

Initialize root;

PQ <- root;

max_cost := root.cost;

while PQ not equal do

current <- PQ;

if (current.bound > max_cost) then

create left_child := next item;

if (left_child.cost > max_cost)

max_cost := left_child.cost;

update best_solution;

end if;

if (left_child.bound > max_cost)

PQ <- left_child;

end if;

create right_child; // it skips packing the next item

if (right_child.bound > max_cost)

PQ <- right_child;

end if;

end if;

end while;

return best_solution and its cost;

end procedure;

I'd like to invite you to join our experienced community of technology professionals in all areas of IT&C, from software and hardware up to consumer electronics at Dev Hardware Forums. As well, be sure to check out the community of our sister site at Dev Shed Forums. We are friendly and we'll do our best to help you.

DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware.

blog comments powered by Disqus

- Division of Large Numbers
- Branch and Bound Algorithm Technique
- Dynamic Programming Algorithm Technique
- Genetic Algorithm Techniques
- Greedy Strategy as an Algorithm Technique
- Divide and Conquer Algorithm Technique
- The Backtracking Algorithm Technique
- More Pattern Matching Algorithms: B-M
- Pattern Matching Algorithms Demystified: KMP
- Coding Standards
- A Peek into the Future: Transactional Memory
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- Learning About the Graph Construct using Gam...
- How to Strike a Match

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials