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?