# Decision tree algorithm

1. May 20, 2015

### Sypha

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?
Thanks

2. May 20, 2015

### phinds

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.

3. May 20, 2015

### Mentallic

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 $g=gcd(v_1,v_2)$ if $g|V$ where v1,v2 are the smaller volumes. This would cut down a lot of computational time.