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