Sum of integers closest to a given number

Question

I have the following problem at hand:
Given an odd number $n > 7$, find a set of non-negative integers $m_7$, $m_8$, ..., $m_{13}$ and $m_{14}$, such that the sum

$m_7\cdot 7 + m_8\cdot 8 + ... + m_{13}\cdot 13 + m_{14}\cdot 14$

comes as close as possible, but does not exceed $n$.
I know that there is not a unique solution, e.g. if $n=33$ there are at least 2 solutions that reach exactly $33$: $m_7 = 1$, $m_{12} = 1$ and $m_{14} = 1$ (everything else $0$) or $m_7 = 3$ and $m_{12} = 1$ (with everything else 0). In such cases I would prefer the solution that has the largest possible values for the coefficients with large subscripts, i.e. $m_{14}$, $m_{13}$, ... .
Is it always guaranteed that there is a solution that can reach $n$ exactly?
Any insights on that problem will be greatly appreciated.

(I guess one can define it as an optimization problem:
Minimize $|n - (m_7\cdot 7 + m_8\cdot 8 + ... + m_{13}\cdot 13 + m_{14}\cdot 14)|$ under the constraint $m_7\cdot 7 + m_8\cdot 8 + ... + m_{13}\cdot 13 + m_{14}\cdot 14 \leq n$.)

Answer 1

Allowing 7 through 14 as summands, I think this can be solved directly without reference to generating functions, the Frobenius problem, the knapsack problem, or linear programming.

Write $n = 14q + r$ with $0 \le r \le 13$.

• If $r=0$, then let $m_{14} = q$ (unspecified coefficients are 0).
• If $1 \le r \le 6$, let $m_{14} = q-1$ and, to take care of the remaining $14+r$, let $m_7 = 1$ and $m_{7+r} = 1$.
• If $r \ge 7$, let $m_{14} = q$ and $m_r = 1$.

This gives you an exact sum of $n$ (for all $n \ge 7$) and maximizes $m_{14}$, the coefficient with the largest subscript.