# Knapsack with an even number of items.

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?

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

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]$

• When do you calculate $DP_{even}$ and $DP_{odd}$? When i and j have what value? Can't figure this bit out... Nov 20 '17 at 19:42
• also, what is the array $c$? what does $c[i]$ mean? Nov 20 '17 at 21:08
• @Makz $c[i]$ is the capacity of item i. It is generaly called weight, but the OP called it $c$. Nov 20 '17 at 23:29
• @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. Nov 20 '17 at 23:30
• 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])$$ Nov 21 '17 at 15:09