3 Replies Latest reply on Jul 22, 2008 2:39 PM by 800282

    "Branch and Bound" algorithm

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