What weights should I buy for my gym? (a case of integer partitioning)

Solution 1:

To make it up to $405$ you could buy: $$\begin{array}{r|ccccc} \text{weight}& 2.5&5&10&25&45\\ \hline \text{pairs}& 1&1&2&1&3 \end{array}$$ The idea is that in any combination of weights you can often replace multiple small weights by a single large weight. For example $2$ pairs of $2.5$'s can be replaced by a $5$, so you will never need $2$ pairs of $2.5$'s. Similarly you will never need $2$ pairs of $5$'s, or $3$ pairs of $10$'s, or $2$ pairs of $25$'s.

You will need $2$ pairs of $10$'s for some combinations, such as $$90=45+2\times(2.5+2\times10).$$ Finally, just buy enough pairs of $45$'s to get up to the desired weight of $405$. These weights get you all the way up to $420$ even.

Finally, instead of $2$ pairs of $10$'s you could also buy $2$ pairs of $5$'s and $1$ pair of $10$'s to reach all combinations. This may save some money, while still getting you up to $410$ total.

Solution 2:

Let's say you want to obtain the values $v_1,...,v_n$ as a sum of nonnegative integer multiples of $w_1,...,w_k$.
I.e. you're looking for a vector $(a_1,..,a_k)$ so that $$ \forall i\in [n]: \exists b_1\in[ a_1],..., b_k\in [a_k]: \sum_{j=1}^n b_j\cdot w_j = v_i $$ This formulation already shows a way to brute-force yourself to the solution:

"function" returns the minimal vector (towards the $||\cdot ||_1$ norm) that fulfills the constraints.

The set $\{\left(a_1,..,a_k\right)\in Z^k\mid a_1+\ldots+a_n=m\}$ is the set of weak compositions of $m$ into $n$ parts.