2
$\begingroup$

I was asked in an interview to create a knapsack of only even items in n*C time, c being the capacity, n being the number of items to choose from. I tried approaching it with a third dimension, where it would be of height n and signify at each ij whether the knapsack with these maxes contains even numbers or not, but I think its incorrect and I can't code it.

Any suggestions?

$\endgroup$
  • $\begingroup$ Well, DP in wikipedia for any (either even or odd) number of items already is $O(nC)$, according to it. $\endgroup$ – rus9384 Oct 25 '17 at 17:07
3
$\begingroup$

You can keep two tables with $n$ rows and $C$ columns:

$DP_{even}$ that saves the best knapsack solution with an even number of itens. $DP_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP_{even}$ you look at the previous best solution of $DP_{odd}$ plus a new item, or of $DP_{even}$ if you don't take the item: $$DP_{even}[i, j] = max(DP_{odd}[i - 1,j - c[i]] + v[i], DP_{even}[i - 1, j]) $$ The same idea goes for $DP_{odd}$ $$DP_{odd}[i, j] = \max(DP_{even}[i - 1,j - c[i]] + v[i], DP_{odd}[i - 1, j]) $$

Your solution will be in $DP_{even}[n, C]$

$\endgroup$
  • $\begingroup$ When do you calculate $DP_{even}$ and $DP_{odd}$? When i and j have what value? Can't figure this bit out... $\endgroup$ – lmaooooo Nov 20 '17 at 19:42
  • $\begingroup$ also, what is the array $c$? what does $c[i]$ mean? $\endgroup$ – lmaooooo Nov 20 '17 at 21:08
  • $\begingroup$ @Makz $c[i]$ is the capacity of item i. It is generaly called weight, but the OP called it $c$. $\endgroup$ – klaus Nov 20 '17 at 23:29
  • $\begingroup$ @Makz It is important that you know already how to solve the simpler version of knapsack using DP. It is the exact same thing, except that you get the previous value from another matrix, instead of the same. $\endgroup$ – klaus Nov 20 '17 at 23:30
  • 1
    $\begingroup$ Both are $n*C$ and you will fill both of them completely. For every i and j, you will put both statements inside the for loop: $$DP_{odd}[i,j]=max(DP_{even}[i−1,j−c[i]]+v[i],DP_{odd}[i−1, j])$$ $$DP_{even}[i,j]=max(DP_{odd}[i−1,j−c[i]]+v[i],DP_{even}[i−1, j])$$ $\endgroup$ – klaus Nov 21 '17 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.