3
$\begingroup$

I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: Variant of the Knapsack Problem.

Please read the previous answer for context; also I'm positive that the formula is still correct, but either my use or understanding of it is incorrect.

Let me illustrate the issue:

  • Item 1: weight=1, value=1
  • item 2: weight=1, value=4
  • item 3: weight=1, value=3

The calculated dp table (total items visited denoted in superscript): $$ \begin{array}{c|ccc} 3 & 1^1 & 5^2 & 8^3 \\ 2 & 1^1 & 5^2 & 7^2 \\ 1 & 1^1 & 4^1 & 4^1 \\ \hline & 1 & 2 & 3 \end{array} $$

Now to find the best two items out of the three ($p=2$), we use Carlos alternate formula $\max\limits_{p=0,j-1}\{T_{i, p}\}$. The best 2 dp table looks as follows: $$ \begin{array}{c|ccc} 3 & 1^1 & 5^2 & 4^2 \\ 2 & 1^1 & 5^2 & 7^2 \\ 1 & 1^1 & 4^1 & 4^1 \\ \hline & 1 & 2 & 3 \end{array} $$ You can clearly see this is wrong--look at the values of $T_{3,3}$ and $T_{2,3}$. Anyway this is how I calculated the table: the first two columns ($j$-items) are identical. The third column ($j=3$) is where we start using the formula.

  • $T_{1,3} = T_{1,2}$
  • $T_{2,3} = T_{i-w_j,j-1,k-1}+v_j = T_{1,j-1,k-1}+v_j = T_{1,j-1,k-1}+v_j = \max\limits_{p=0,j-1}\{T_{i, p}\} + v_j = \max\limits_{p=0,1}\{T_{1, p}\} + v_j = \max\{T_{1,1}, T_{1,2}\} + v_j = \max\{1,4\} + 3 = 4 + 3 = 7$
  • $T_{3,3} = T_{i-w_j,j-1,k-1}+v_j = T_{2,j-1,k-1}+v_j = T_{2,j-1,k-1}+v_j = \max\limits_{p=0,j-1}\{T_{i, p}\} + v_j = \max\limits_{p=0,1}\{T_{2, p}\} + v_j = \max\{T_{2,1}, \require{enclose}\enclose{updiagonalstrike}{T_{2,2}}\} + v_j = \max\{1,\enclose{updiagonalstrike}{5}\} + 3 = 1 + 3 = 4$

Now the reason the $T_{2,2} (5)$ is crossed-out because the total items visited count for that entry is already $2$, so I'm assuming we just skip it? But (un?)fortunately the two best items are $j=2$ and $j=3$.

For reference, I implemented using the k-dimension and that one gives the correct results. However, I'm still curious as to why this specific formula isn't working; I'm sure I'm doing something silly--please help me find it =)

EDIT: Dp tables for $k=1,2,3$

K=1 $ \begin{array}{c|ccc} 3 & 1^1 & 4^1 & 4^1 \\ 2 & 1^1 & 4^1 & 4^1 \\ 1 & 1^1 & 4^1 & 4^1 \\ \hline & 1 & 2 & 3 \end{array} $

K=2 $ \begin{array}{c|ccc} 3 & 1^1 & 5^2 & 7^2 \\ 2 & 1^1 & 5^2 & 7^2 \\ 1 & 1^1 & 4^1 & 4^1 \\ \hline & 1 & 2 & 3 \end{array} $

K=3 $ \begin{array}{c|ccc} 3 & 1^1 & 5^2 & 8^3 \\ 2 & 1^1 & 5^2 & 7^2 \\ 1 & 1^1 & 4^1 & 4^1 \\ \hline & 1 & 2 & 3 \end{array} $

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ thanks again for the follow-up question. I do promise to come back to it as soon as I have time. Just for clarification: rows are subscripted with index $i$ and columns are referenced with index $j$, right? Additionally, I understand that the subindices of $T$ are given in the order $i, j$ (ie., row, column). Thus, I can see that in the second table, $T_{3,3}$ is wrong, but $T_{2,3}$ is correct ... (it seems from the sentence just below the second table that $T_{2,3}$ should be wrong) $\endgroup$ – Carlos Linares López Aug 25 '15 at 1:31
  • $\begingroup$ Thanks @Carlos. The second table should look exactly like the second to last table (where $k=2$). Maybe I completely misunderstood your alternate formula but I thought we could calculate best-$p$ items of $n$-items without having to calculate a third index $k$. $\endgroup$ – Saad Malik Aug 25 '15 at 5:18

Your Answer

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

Browse other questions tagged or ask your own question.