FInding the combination with the least number of elements from and array of integers, given an integer sum - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-05-24T19:26:00Z https://cs.stackexchange.com/feeds/question/98299 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/98299 1 FInding the combination with the least number of elements from and array of integers, given an integer sum fendrbud https://cs.stackexchange.com/users/94717 2018-10-08T10:12:07Z 2019-05-06T19:03:55Z <p>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.</p> <p>The gready algorithm I've written is:</p> <pre><code>Function min_comb(array, value) min = 0 for i in 1:length(array) if array[i] &lt;= value min += floor(value / array[i]) value = value % array[i] end end return min end </code></pre> <p>which works fine for Example 1 below, but of course not for Example 2.</p> <p>Example 1: If given an array <span class="math-container">$A=[1000,500,100,20,5,1]$</span> and a sum <span class="math-container">$S=1226$</span>, the least number of combinations would be <span class="math-container">$N=6$</span> (<span class="math-container">$1000+100+100+20+5+1$</span>).</p> <p>Example 2: If given an array <span class="math-container">$A=[4,3,1]$</span> and a sum <span class="math-container">$S=6$</span>, the least number of combinations would be <span class="math-container">$N=2$</span> (<span class="math-container">$3+3$</span>).</p> <p>How should I go about solving this problem?</p> https://cs.stackexchange.com/questions/98299/-/98311#98311 0 Answer by xskxzr for FInding the combination with the least number of elements from and array of integers, given an integer sum xskxzr https://cs.stackexchange.com/users/83244 2018-10-08T13:39:24Z 2018-10-08T13:39:24Z <p>Let <span class="math-container">$f(s, i)$</span> be the minimum number of elements (only the first <span class="math-container">$i$</span> elements of the array are considered) required to sum up to <span class="math-container">$s$</span>, then we have <span class="math-container">$$f(s,i)=\min_{0\le j\le s/A[i]}\left\{j+f(s-jA[i], i-1)\right\}.$$</span></p> <p>You can use this formula to compute <span class="math-container">$f(s,i)$</span> for all <span class="math-container">$s$</span> and <span class="math-container">$i$</span>. With knowing <span class="math-container">$f$</span>, you can figure out the optimal combination. This is left as an exercise for you.</p> https://cs.stackexchange.com/questions/98299/-/101182#101182 0 Answer by gnasher729 for FInding the combination with the least number of elements from and array of integers, given an integer sum gnasher729 https://cs.stackexchange.com/users/17408 2018-12-07T16:32:35Z 2018-12-07T16:32:35Z <p>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. </p> <p>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. </p> <p>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. </p> <p>In your second example the greedy algorithm uses 3 numbers. Starting with a four cannot improve, but 3+3 does. </p>