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?

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

1 Answer 1

Reset to default
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]$

Improve this answer
$\endgroup$
7
  • $\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
    Commented Nov 20, 2017 at 19:42
  • $\begingroup$ also, what is the array $c$? what does $c[i]$ mean? $\endgroup$
    – lmaooooo
    Commented Nov 20, 2017 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
    Commented Nov 20, 2017 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
    Commented Nov 20, 2017 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
    Commented Nov 21, 2017 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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