Knapsack problem 0/1 with even number of items

Question

So I need to solve the knapsack problem, but I need to make sure that the end solution consists of an even number of items.

I found this on an already existing question:

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

But how do I initialize both arrays, since when I intitialize them with 0 in the first row both arrays are going to be the same? Or am I making a false conclusion?

Edit: I already know how to solve the knapsack problem normally, so you don't need to explain that.

Answer 1

For the base case, the value is often decided manually based on the context of the problem. What should be the base value?

It is easy to see that $DP_{even}[0,0]$ should be $0$, and $DP_{even}[0,j]$ for $j>0$ should be $-\infty$. This is because the highest value you can get with considering none of the items and cost nothing is trivially 0, but the case where you consider none them but still cost something is impossible, hence we can safely assign it $-\infty$.

Now let's look at $DP_{odd}$. You might think that $DP_{odd}[0,0]$ is $0$, but following your definition, $DP_{odd}[0,0]$ means the highest value you can get with considering none of the items, and take an odd number of items and costs nothing. Notice the contradiction in this statement? You don't consider any items, then obviously you couldn't have taken an odd number of items! The same argument holds for all $DP_{odd}[0,j]$ for $j\geq 0$. Hence, they are all assigned $-\infty$.

To summarize, the base case is very similar. Both $DP_{even}[0,j]$ and $DP_{odd}[0,j]$ are mostly $-\infty$, except $DP_{even}[0,0]$ which is $0$. Now, you can safely run your recurrence relations on top of the base cases.

Answer 2

Note: At the time of my writing, the only other answer to this question seems incorrect. I do not agree that $DP_\text{e}(0,j) = -\infty$ for all $j > 0$. Whether the backpack is full ($j = 0$) or has space remaining ($j > 0$) after all items are considered is inconsequential. Provided the total number of items in the knapsack is an even number, the solution is feasible but no further value may be gleaned. Hence, $DP_\text{e}(0,j) = 0$ for all $j \ge 0$.

Let's suppose the 0-1 knapsack problem takes the following form: \begin{align} \max~ & \sum_{i=1}^n c_i x_i \\ \text{s.t.}~ & \sum_{i=1}^n a_i x_i \le b, \\ & x_i \in \{0, 1\}, \quad i=1,\ldots,n. \end{align} Then the value functions for the dynamic programming approach may be defined as follows: \begin{equation} DP_\text{e}(i, j) = \begin{cases} -\infty, & j < 0 \\ 0, & j \ge 0~\text{and}~i = 0 \\ \max\left\{ DP_\text{e}(i-1,j), DP_\text{o}(i-1,j-a_i)+c_i \right\}, & j \ge 0~\text{and}~i > 0 \end{cases} \end{equation} and \begin{equation} DP_\text{o}(i, j) = \begin{cases} -\infty, & j < 0~\text{or}~i = 0 \\ \max\left\{ DP_\text{o}(i-1,j), DP_\text{e}(i-1,j-a_i)+c_i \right\}, & j \ge 0~\text{and}~i > 0 \end{cases}. \end{equation} In these functions, $i$ indicates the item under consideration and $j$ indicates the remaining knapsack capacity. Items are considered in descending order, and the value $i=0$ indicates that no items remain for consideration (i.e., $i=0$ is a base state regardless of $j$).

The function $DP_\text{e}(i,j)$ represents the answer to the following question: With an even number of items already in the knapsack and with $j$ space remaining, how much value may yet be gleaned from items $1,\ldots,i$ if an even number of items must end up in the knapsack? The function $DP_\text{o}(i,j)$ represents the answer to the same question but starting with an odd number of items already in the knapsack. If $\sum_{i=0}^n x_i$ must be even, then the best objective value is $DP_\text{e}(n, b)$. If odd, then the best objective value is $DP_\text{o}(n, b)$.