Bi Knapsack Dynamic Programming Algorithm

Definition

Bi Knapsack Dynamic Programming Algorithm

For Bi Knapsack, define
$T_i(s_1,s_2)=\max \{|J|:J\subseteq \{1,\dots ,i\},{\sum }_{j\in J}{a}_j\le s_1,{\sum }_{j\in J}{b}_j\le s_2\}.$
Compute all states for $0\le i\le n$, $0\le s_1\le S_1$, $0\le s_2\le S_2$. The final entry $T_n(S_1,S_2)$ is the optimal cardinality. The running time is pseudopolynomial in the two capacities.

Recurrence

Budgets are upper bounds, not exact weights

Initialise $T_0(s_1,s_2)=0$ for all budgets: the empty selection fits every nonnegative pair. This differs from an exact-weight table, in which most base states would be unreachable.

To process item $i$, skipping gives $T_{i-1}(s_1,s_2)$. If $a_i\le s_1$ and $b_i\le s_2$, taking it gives
$1+T_{i-1}(s_1-a_i,s_2-b_i).$

Both capacities decrease when taking one item. The predecessor lies in layer $i-1$, not the current layer: the same item cannot be selected twice. Take the larger of the skip value and the take value when the latter is available.

Pseudocode and reconstruction

for every budget s1,s2:
    T[0,s1,s2] = 0
for i = 1,...,n:
    for s1 = 0,...,S1:
        for s2 = 0,...,S2:
            T[i,s1,s2] = T[i-1,s1,s2]
            if a[i] <= s1 and b[i] <= s2:
                T[i,s1,s2] = max(T[i,s1,s2],
                    1 + T[i-1,s1-a[i],s2-b[i]])
return T[n,S1,S2]

To return a subset as well as its value, backtrack from $(n,S_1,S_2)$. If the value equals the skip predecessor, skip that item. Otherwise take it, subtract both sizes from the budgets, and move to layer $i-1$. Equality can be resolved by skipping. Continue until layer zero.

Correctness

Induction on the number of available items

Base layer

With no available items, the empty set is the only selection and has cardinality zero. Every base entry is correct.

Upper bound every feasible selection

Assume layer $i-1$ is correct. A feasible selection either omits item $i$, giving value at most the skip predecessor, or contains it. In the latter case the remaining items fit the two reduced budgets, giving value at most one plus the take predecessor.

Attain each candidate

An optimal skip predecessor remains feasible. An optimal take predecessor together with item $i$ fits both budgets whenever the take condition holds. Therefore the maximum of the available candidates is both an upper bound and attainable. This establishes the invariant, and hence the final optimum and backtracking procedure.

State count and encoding length

The table contains exactly $(n+1)(S_1+1)(S_2+1)$ cells, with constant many arithmetic operations per cell. Values lie in $\{0,\dots ,n\}$ and use $O(\log (n+1))$ bits. Two rolling layers suffice for the value alone; storing all layers permits the direct reconstruction above.

The capacities are numerical bounds, not their bit lengths. For example, a capacity $S=2^b$ needs only $b+1$ binary digits, but an axis indexed by $0,\dots ,S$ has $2^b+1$ positions. With two such capacities, the table has $(2^b+1{)}^2$ positions per layer. This shows why the stated implementation need not be polynomial in binary input length.

Under unary encoding, both capacities and the number of items are bounded by the input length, so the state count is polynomial. This pseudopolynomial algorithm does not imply an FPTAS: Bi Knapsack has no FPTAS unless P equals NP.