Pseudo-Polynomial Dynamic Programming is about Compression

Pseudo-polynomial dynamic programming has two opposite movements.

First, it compresses a large combinatorial search space into a table of states. For knapsack, brute force asks which of the $2^n$ subsets should be chosen. The dynamic programme instead keeps a table entry $T[i,s]$: after considering the first $i$ items, what is the best value at capacity $s$?

Many different subsets can lead to the same state $(i,s)$. Once they do, the algorithm forgets the histories and keeps only the best value.

That is the compression: many histories collapse into one table entry.

The Expansion

The second movement goes in the other direction. The state coordinate $s$ ranges over every capacity value $0,1,\dots ,S$.

If $S$ is stored in binary, then the input contains only ${\ell }_S(I)=\lceil {\log }_2(S+1)\rceil$ bits for this capacity. But the table has $S+1$ columns. In other words, one compact field expands into a unary-sized interval of states:

$$S\approx 2^{{\ell }_S(I)}.$$

So pseudo-polynomial DP compresses the combinatorial part while expanding the numeric part.

The Point

For knapsack, dynamic programming replaces the brute-force search space $2^n$ by a table of size roughly $nS$. For Bi Knapsack, the table becomes $T[i,s_1,s_2]$ with size $O(n{S}_1{S}_2)$.

This can be a real compression of the subset search. But it is not necessarily ordinary polynomial time, because the numeric dimensions $S,S_1,S_2$ may be exponentially larger than their binary encodings.

Therefore, pseudo-polynomial dynamic programming compresses histories into states, but may expand compact numeric inputs into unary-sized table dimensions.