19 March 2015
Problem overview
Given an array of n integers, A = { a1, a2, a3, …, an }, and another integer k representing the expected sum. Select zero or more numbers from A such that the sum of these numbers is as near as possible, but not exceeding, the expected sum (k). Example: a = { 2, 4, 6, 8 }. k = 15
This is a classical Dynamic Programming problem, there is the 0/1 version which you can use only once each element of the array A and the unbounded version where you can use unlimited times elements from the array, this version is the unbounded one.
Algorithm analysis
The idea is that for a state S[i] test if each of the numbers from the array fit on that current sum and if that new sum obtained is better than the one before, where the closest number from sum will be either S[i] or S[i - A[j]] + a[j].
Code in Java
public static int solveKnapsack(int[] a, int k) {
<span class="kt">int</span><span class="o">[]</span> <span class="n">f</span> <span class="o">=</span> <span class="k">new</span> <span class="kt">int</span><span class="o">[</span><span class="n">k</span> <span class="o">+</span> <span class="mi">1</span><span class="o">];</span>
<span class="c1">// base case</span>
<span class="n">f</span><span class="o">[</span><span class="mi">0</span><span class="o">]</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span><span class="o">;</span> <span class="n">i</span> <span class="o"><=</span> <span class="n">k</span><span class="o">;</span> <span class="n">i</span><span class="o">++)</span> <span class="o">{</span>
<span class="k">for</span> <span class="o">(</span><span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="mi">0</span><span class="o">;</span> <span class="n">j</span> <span class="o"><</span> <span class="n">a</span><span class="o">.</span><span class="na">length</span><span class="o">;</span> <span class="n">j</span><span class="o">++)</span> <span class="o">{</span>
<span class="k">if</span> <span class="o">(</span><span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">]</span> <span class="o"><=</span> <span class="n">i</span><span class="o">)</span> <span class="o">{</span>
<span class="n">f</span><span class="o">[</span><span class="n">i</span><span class="o">]</span> <span class="o">=</span> <span class="n">Math</span><span class="o">.</span><span class="na">max</span><span class="o">(</span><span class="n">f</span><span class="o">[</span><span class="n">i</span><span class="o">],</span> <span class="n">f</span><span class="o">[</span><span class="n">i</span><span class="o">-</span><span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">]]</span> <span class="o">+</span> <span class="n">a</span><span class="o">[</span><span class="n">j</span><span class="o">]);</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="o">}</span>
<span class="k">return</span> <span class="n">f</span><span class="o">[</span><span class="n">k</span><span class="o">];</span>
}