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

    "Branch and Bound" algorithm

    800383
      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
          807589
          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
            800383
            Hey, thanks a lot! The 0-1 Knapsack algorithm seems to be exactly what I was looking for!
            • 3. Re: "Branch and Bound" algorithm
              800282
              Perhaps a bit late, but you could also try to search for "bin packing problem" for more information on the matter.