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

Question

I am trying to solve for possible combinations of weights that would be appropriate for use in my home gym. I have been told that this is a case of integer partitioning, but I am not sure how to solve it and would appreciate some guidance (or even better a solution!).

Given that I am quarantined at home, I want to buy weight plates for use in a home gym. In my gym, I have a 45lb bar. I attach weight plates to the bar in pairs, so I always purchase and use plates in pairs. So, if I buy 1 pair of 2.5lb plates, I would be able to use the bar at weights of 45lb or 50lb (since plates must always be used in pairs).

I want to determine how many pairs of 2.5lb, 5lb, 10lb, 25lb, and 45lb plates I need to ensure that I can use my bar at weights of 45 to 405lb in 5lb increments (so options would include 45, 50, 55, 60,..., 395,400, 405). I want to minimize the number of smaller plates that I buy (so mostly get 45s and then get some minimum number of pairs of each of the smaller plates to ensure all possible combinations are attainable).

How might I approach this problem?

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

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