3 Replies Latest reply: Jul 22, 2008 9:39 AM by 800282

# "Branch and Bound" algorithm

I need a Java implementation of "Branch and Bound" algorithm or a library that will help me implemen it on my own.
The problem I need to solve is as follows:

In human language:

I want to make a program that will find the optimal combination of files to be burned onto a DVD. The sum of the file sizes should be maximized but can not be over 4483 MB. The file can eighter be burned whole or not burned at all ( thus X = {0, 1} ).

Mathematical model:
``````max f(x) = a1X1 + a2X2 + a3X3 + ... + anXn

X1 + X2 + X3 + ... + Xn <= 4483 (the capacity of a DVD in MB)
X = {0, 1}``````
Any help is appreciated.
• ###### 1. Re: "Branch and Bound" algorithm
Sounds like you might want a simple greedy algorithm. Sort by filesize, then start adding the largest files; if one would put it over the limit, skip it and try the next.

Of course, it may not always be optimal - but it'll be a heck of a lot easier to implement and take a heck of a lot less time to run.

If you want an optimal solution, you need to use dynamic programming. If you want to do it, read through [this short pdf|http://web.archive.org/web/20060906091630/www.csl.mtu.edu/cs4321/www/Lectures/knapsack2.pdf] .
• ###### 2. Re: "Branch and Bound" algorithm
Hey, thanks a lot! The 0-1 Knapsack algorithm seems to be exactly what I was looking for!
• ###### 3. Re: "Branch and Bound" algorithm
Perhaps a bit late, but you could also try to search for "bin packing problem" for more information on the matter.