 <p>Return a pair of values containing the weight and value:</p> <pre><code>pair&lt;int, int&gt; knapsack(int N, int budget) { if((!N) || (!budget)) return pair&lt;int, int&gt;(0, 0); pair&lt;int, int&gt; local(N, budget); if(hash_memo[local].second) return hash_memo[local]; pair&lt;int, int&gt; b = pair&lt;int, int&gt;(0, 0); pair&lt;int, int&gt; a = knapsack(N-1, budget); if(budget &gt;= arr[N-1].first) { pair&lt;int, int&gt; c = knapsack(N-1, budget - arr[N-1].first); b = pair&lt;int, int&gt;(c.first + arr[N-1].first, c.second + arr[N-1].second); } if(a.second &gt; b.second) { return hash_memo[local] = a; } return hash_memo[local] = b; } </code></pre>