0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.