Given integers $m$ and $n$, and a vector $\mathbf{v} \in \mathbb{Z}^n \setminus \{ \mathbf{0}_n \}$,
$$ \begin{array}{ll} \underset {\mathbf{w} \in \mathbb{N}^n} {\text{minimize}} & \sum\limits_{i=1}^n w_i \\ \text{subject to} & \mathbf{v} \cdot \mathbf{w} = m \end{array} $$
How would one solve this algorithmically? I know this is a variation of the infamous coin change problem, but are there better solutions to something like a dynamic programming approach?
Example
If we have $\mathbf{v} = [2,4,5]^\top$ and $\mathbf{v} \cdot \mathbf{w} = 16$, we find that the weight vector is $\mathbf{w} = [0,4,0]^\top$.
First, there are cases where there are no solutions. E.g., $(2,2)\cdot w=17$ has no solution in integers, for obvious reasons. Worse, $(8,9)\cdot w=10$ has solutions in integers, but not in positive (or even nonnegative) integers.
So, let's assume we have $a,b,m$ positive integers with $\gcd(a,b)=1$ such that $ax+by=m$ has a solution $x=x_0$, $y=y_0$ in positive integers $x_0,y_0$. Then all the solutions in integers are given by $x=x_0+tb$, $y=y_0-ta$, where $t$ is an arbitrary integer. To keep things positive, you must have $t>-x_0/b$ and $t<y_o/a$. So you can just look at all the values of $t$ in that range, and choose the one that minimizes $x+y$.
But, wait! You haven't told us what it means to minimize $w$! It's a vector, not a number, so you have to have some way to compare two vectors to see which one is bigger, and you haven't told us how you plan to do that. So, that's your first job – until you do that, there's no sensible answer to your question.Now, everything I've done here is for the case $n=2$. That's because cases with $n>2$ are a lot harder. But the case $n=2$ should give you something to think about.