Given any one instance of the knapsack problem, consider the sub-instance defined by items 1,…,j and capacity u and v (j≤n,u≤c 1,v≤c 2).
where (tilde N = bigcup nolimits _{k = 1}^{l} {{N_{k}}} ), and assume that ({f_{l}}left ({tilde c} right) = - infty ) if the sub-instance has no feasible solution.
Given a pair of integers l (1≤l≤r) and ({tilde c}) (left ({0 le tilde c le c} right)), consider the sub-instance of MCKP consisting of subset N 1,…,N l and capacity ({tilde c}).
We use the notation of Section 5 regarding multiple string instances, positions, and sub-instances.
Therefore, all inside properties of strict sub-instances of S X, Y are available according to the pre-condition.
Characters and positions in such sub-instances are indexed according to the same indexing as of the original string s.
In addition, we use as arguments for ρ and τ sub-instances of the form S Q, Q', where Q' is a local increment of Q.
Say we are interested in finding solutions to sub-instances of the form (X, Y ∖ { y}, w) for every y ∈ Y.
Note that in such computations, all entries in the multiplied sub-matrices already contain the computed solutions for the corresponding sub-instances.
Therefore, it follows from the postcondition that once the computation terminates all entries in matrices EDT α and ED contain the solutions for the corresponding sub-instances.
The algorithm maintains the following matrices for storing solutions to sub-instances of the input which occur along the recursive computation.
