# Combinatorial optimization problem

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem.

If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can I decide which volumes to use to get the minimum wastage? Some examples:

If $V_{required} =300$ and my smaller volumes are $V_1=60$ and $V_2=150$, one would use $2V_2$.

If $V_{required}=240$, then one would use $4V_1$.

If $V_{required}=330$ one would use $3V_1+V_2$.

Finally if $V_{required}=250$ one would use $2V_1+V_2$ with $20$ units 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.

• You must use $a_1V_1+a_2V_2$ for some $a_1$, $a_2$ satisfying $0\le a_1\le V/V_1$, $0\le a_2\le V/V_2$, so there are only finitely many possibilities you have to test. May 21, 2015 at 12:42

As Gerry Myerson commented, for two volumes, the number of solutions is quite limited, so let us consider it with $p$ volumes.
Call $n_i$ the number of times volume $V_i$ should be used and $V_{required}$ the required volume. So, the waste $W$ is $$W=\sum_{i=1}^p n_i V_i-V_{required}$$ I then suppose that we could define an objective function $$\Phi(n_1,n_2,\cdots,n_p)=\Big(\sum_{i=1}^p n_i V_i-V_{required}\Big)^2$$ we need to minimize subject to bound constraints $0\leq n_i\leq \frac {V_{required}}{V_i}$, and a linear constraint $W\geq0$.