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. |
