Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

Question

A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically:

Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where each $a_{i+1} > a_i$ and each $a_i > 0$, design an algorithm that finds the minimum number of such $a_i$ that their sum adds up to $N$. You can use each $a_i$ an unlimited number of times. You may assume $N$ is a possible sum for any $L$.

Example: $L = [1, 3, 5]$. $N = 10$. The optimal choice is $5 + 5$. A possibility is using $10$ $1$'s, but that is not optimal.

I thought I found the optimal solution using a greedy algorithm, where we start with $0$ add the largest integer from $L$ without going over.

But my greedy algorithm fails in this case:

Integers: $[1, 5, 7]$, $N = 10$; greedy algorithm gives $7+1+1+1$, but optimal solution is $5+5$.

The people I've talked to suggested taking a Dynamic Programming approach, but I am not quite comfortable with DP. What suggestions or hints do you have for thinking of a DP approach? I think I should approach this recursively, but in what way? Should I keep breaking it down to halves until I find individual components (kinda like mergesort), and see what numbers these components add up to in $L$?

Answer 1

You start with an array $A$ from 0 to N and initialize every value with $\infty$ (or some very large number). Then you set $A[0] = 0$.

Then you loop the following until no more changes occur:

For each number $0 \leq n \leq N$ and for each integer $l\in L$ you update $A[n+l] = min(A[n+l],A[n]+1)$ (don't forget to check for array boundary violations)

When finished, the value of $A[n]$ should contain the minimum number of integers from your list that sum up to $n$.

Expected runtime of this is pretty bad (assuming you have a huge $N$ and $L = \{1,N\}$, as you will update values for $n<N$ for quite some time until you've found your solution.

You can optimize it a bit by observing, that in each iteration, the assigned values increase by one and thus, if some value has been assigned it will not be updated anymore. Therefore, as soon as $A[n] \neq \infty$ you can stop as the lowest value has been found.

Also you can keep track of a "frontier", i.e those indices $i$, for which $A[i]$ has been assigned in the last iteration. You can implement this with a queue, where you add $n+l$ to the queue if the minimum is lower than the previously found value and don't iterate over all $n$ but take the first element from the queue, which has been initialized with $Queue.add(0)$.

The resulting runtime should be $\approx\mathcal O (K\cdot r)$ (or something similar, e.g. $\mathcal O (K^2\cdot r)$) where $K$ is the number of integers in your set and $r$ is the result.

You could improve it a little bit if you replace the queue with a priority queue (e.g. a maxheap).

Alternatively you could precompute some multiples of your numbers (e.g. if $N=10^6-1$ and you have 1 and 1000, you would first determine the values for the largest multiple of each number that is below $N$ (999999*1 and 999*1000) and assign those directly).