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

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?

• Are repetitions allowed? Like can a particular array element be considered twice? Also I suggest you have a look at the standard subset sum problem and see if you can take it from there. – Arka Pal Oct 8 '18 at 11:35

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.