Finding the n-best items in a 0/1 Knapsack
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 <PERSON> 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 <PERSON> alternate formula $\max\limits_{p=0,j-1}{T_{i, p}}$. 835
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. 490