1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Decision tree algorithm

  1. May 20, 2015 #1
    Hi all,
    Im having trouble making a general algorithm for what at first glance appears to be a simple problem. If I have a volume (V) that can be made from two smaller, different volumes how can I decide which volumes to use to get the minimum wastage? So for example if V(required)=300 and my smaller volumes are 60 and 150, one would use 2*150. If V(required) was 240 one would use 4*60. If however V(required) is 330 one would use 1*150+(3*60); finally if V(required)=250 one would use 1*150+(2*60) with 20units wastage. Is there a way to decide on the best combination for a given volume and two smaller, given volumes for the general case, minimizing wastage?
  2. jcsd
  3. May 20, 2015 #2


    User Avatar
    Gold Member

    I seem to recall that a good general solution is to fit in as many of the larger as you can and then fill will as many smaller as needed. This will not be the best solution in every possible case, though, so it's NOT a generic optimization solution.
  4. May 20, 2015 #3


    User Avatar
    Homework Helper

    To check that an exact solution exists, if either of the smaller volumes are not a multiple of V then you're dealing with a linear diophantine equation that is restricted to positive solutions. You can run an algorithm that follows that procedure, otherwise I'd use a brute force method that follows phinds' suggestion to find the best solution.

    Don't forget to divide through by [itex]g=gcd(v_1,v_2)[/itex] if [itex]g|V[/itex] where v1,v2 are the smaller volumes. This would cut down a lot of computational time.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook