1
$\begingroup$

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$?

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/tags/dynamic-programming/info $\endgroup$ – D.W. Oct 4 '18 at 6:32
  • 1
    $\begingroup$ Hint: Every representation of $N \neq 0$ as a sum of 1's, 3's, and 5's, is either a representation of $N-1$ plus 1, or of $N-3$ plus 3, or of $N-5$ plus 5. $\endgroup$ – Yuval Filmus Oct 4 '18 at 7:24
  • 1
    $\begingroup$ What exactly do you mean by “smallest combination”? Is ten 1’s (only one element used) smaller or larger than 3 plus 7 (two elements used)? There’s the old saying “you can’t get what you want until you know what you want”. And when you answer avoid words like “obviously” or “of course”. $\endgroup$ – gnasher729 Oct 4 '18 at 12:48
  • $\begingroup$ Sorry, I meant the smallest number of integers. They don't have to be distinct. So, if we're given $1, 3, 7$ as our integers and $N = 10$, then the smallest number of integers we could use to get $10$ would be 2, since $7 + 3 = 10$. Using 10 1's here would result in 10 integers, which isn't optimal. $\endgroup$ – LeetCoder Oct 4 '18 at 14:41
  • $\begingroup$ LeetCoder, please update your question to include any clarifications. People are not expected of reading the comments nor does the search engines as I would assume. $\endgroup$ – Apass.Jack Oct 4 '18 at 17:17
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.