FInding the combination with the least number of elements from and array of integers, given an integer sum

Question

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm which doesn't find the optimal solution, however I'm having problems finding the optimal solution using dynamic programming.

The gready algorithm I've written is:

Function min_comb(array, value)
    min = 0
    for i in 1:length(array)
        if array[i] <= value
            min += floor(value / array[i])
            value = value % array[i]
        end
    end
    return min
end

which works fine for Example 1 below, but of course not for Example 2.

Example 1: If given an array $A=[1000,500,100,20,5,1]$ and a sum $S=1226$, the least number of combinations would be $N=6$ ($1000+100+100+20+5+1$).

Example 2: If given an array $A=[4,3,1]$ and a sum $S=6$, the least number of combinations would be $N=2$ ($3+3$).

How should I go about solving this problem?

Answer 1

Let $f(s, i)$ be the minimum number of elements (only the first $i$ elements of the array are considered) required to sum up to $s$, then we have $$f(s,i)=\min_{0\le j\le s/A[i]}\left\{j+f(s-jA[i], i-1)\right\}.$$

You can use this formula to compute $f(s,i)$ for all $s$ and $i$. With knowing $f$, you can figure out the optimal combination. This is left as an exercise for you.

Answer 2

In general, the problem is very hard. In your special case where every number divides the next higher one, it is trivial. Even in cases like [5, 2, 1], You can prove an optimal solution doesn’t contain two 1s (because one 2 is better) or three 2s (because 5+1 is better) or 2+2+1 because 5 is better.

So you examine the numbers to find any such restrictions. Then you use the greedy algorithm which gives a lower bound for the number of integers you need, then do a systematic search.

In your example, you found a solution with six integers using the greedy method. you can take one 1000, but you can’t add another 1000 or 500. You must add 100 since 1000+4*20 is too small. You must add another 100 since 1100+3*20 is too small. Then you must add 30, then 5 and don’t have enough numbers. You can’t use two 500s because one 1000 is better. One 500 only lets you reach 900, and no 500 only lets you reach 500. Your solution is optimal.

In your second example the greedy algorithm uses 3 numbers. Starting with a four cannot improve, but 3+3 does.