## 3 0/1-KP Solving by DP Transformation to List-Based Time-Space Reduction
### Preprocessing of the DPT-List\({}_{\text{TSR}}\) Algorithm  
In our preprocessing (Algorithm 7), two (temporary) F-lists of e-nodes (the previous F-list \(j-1\) and the current F-list \(j\)) must be built first; see Figure 5 (\(j=0\) to \(n-1\)). Since the previous F-list \(j-1\) can inherit all e-nodes of object 0 to object \(j-1\), the current F-list \(j\) can be constructed from F-list \(j-1\) (to inherit the previous e-nodes and fulfill the current F-list \(j\) with new e-nodes before keeping only the original e-nodes in another B-list \(L_{j}\)). Our preprocessing can reduce the computing time and the using space on a variety of datasets, such as O(\(n^{2}\)) in the best case and O(\(n\)C) in the worst case, as proven in Section 5.2. The current F-list \(j\) of object \(j\) (\(w_{j}\), \(p_{j}\)) can be created in two main steps. In Step 1 (Algorithm 7: Line 3), some e-nodes (\(cn=(tp,d)\)) from the head of F-list \(j-1\) are copied to F-list \(j\) (while (\(cn.tp<p_{j}\) and \(cn.d<w_{j}\))). In Step 2 (Algorithm 7: Lines 4-10 (to fulfill F-list \(j\) with new e-nodes)), from each e-node (\(en\)) of F-list \(j-1\) (head to tail) Step 2.0 checks to inherit each remaining e-node (from step 1) to F-list \(j\) (in a proper location) if it is worth (see detail in Section 5.1), Step 2.1 computes (\(d=en.d+w_{j}\), \(tp=en.tp+p_{j}\)), and Step 2.2 adds new e-node to tails of F-list \(j\) and B-list \(j\) if (\(d\leq\) C and \(tp>\) TP). In this step, the desired TP (at \(d=en.d+w_{j}\)) can be decoded (from \(d\) and \(n_{1}\) in F-list \(j-1\)). Figure 5: An example of preprocessing (\(n=5\), \(C=18\)): (**a**) \(n\)xC array (_tp_) by the basic DP and (**b**) two F-lists and \(n\) B-lists by DPT-List\({}_{\text{TSR}}\) for objects \(j=0\)–4. For example (\(n=5\), \(C=18\)), \(P=\{4\), \(10\), \(6\), \(9\), \(8\}\) and \(W=\{8,15\), \(4\), \(5\), \(12\}\), Figure 5a shows the B-list reduction (right) of seven original e-nodes (see detail in Figure 5b), compared to total profits = \(n\times C=90\) elements (left) of the basic DP. Figure 5b displays the preprocessing of DPT-List\({}_{\text{TSR}}\) from \(j=0\) to \(4\). * For object \(j=0\) (\(w_{0}=8\), \(p_{0}=4\)), Step 1 copies the first e-node \(cn=(tp,d)=(0,0)\) of F-list \(j-1\) to F-list \(j\) (since \(cn.tp<p_{0}\) and \(cn.d<w_{0}\)). In Step 2 (from head of F-list \(j-1\)), at e-node \(en=(0,0)\), Step 2.1 computes \(d=en.d+w_{0}=8\), \(tp=en.tp+p_{0}=4\), and decode TP = \(0\) [\(n_{1}.d=0\), \(n_{1}.tp=0\)), (\(n_{2}.d=C=18\), \(n_{2}.tp=0\))]. Since \(d<C\) and \(tp=4>\) TP = \(0\), Step 2.2 adds new e-node = (\(4\), \(8\)) in F-list \(j=0\) and B-list \(L_{0}\). * For object \(j=1\) (\(w_{1}=15\), \(p_{1}=10\)), Step 1 copies (\(0\), \(0\)), (\(4\), \(8\)) of F-list \(j-1\) to F-list \(j\) (while \(cn.tp<p_{1}\) and \(cn.d<w_{1}\)). In Step 2, at e-node \(en=(0,0)\) of F-list \(j-1\), compute \(d=15\), \(tp=10\), TP = \(4\) (\((n_{1}.d=8\), \(n_{1}.tp=4)\)), (\(n_{2}.d=C=18\), \(n_{2}.tp=4\))). Since \(tp=10>\) TP = \(4\), add new e-node (\(10\), \(15\)) in F-list \(j=1\) and B-list \(L_{1}\). At \(en=(4,8)\), \(d=8+15\)\(=23>C\) (no new e-node added). * For object \(j=2\) (\(w_{2}=4\), \(p_{2}=6\)), Step 1 copies (\(0\), \(0\)) of F-list \(j-1\) to F-list \(j\). In \(\text{\it Step 2}\), at \(en=(0,0)\) of F-list \(j-1\), \(d=4\), \(tp=6>\) TP = \(0\), add new e-node (\(6\), \(4\)) in F-list \(j=2\) and B-list \(L_{2}\). At \(en=(4,8)\) of F-list \(j-1\), \(d=8+4=12\), \(tp=4+6=10>\) TP = \(4\), add new e-node (\(10\), \(12\)). At \(en=(10\), \(15\)), \(d=15+4=19>C\) (no new e-node added). * For object \(j=3\) (\(w_{3}=5\), \(p_{3}=9\)), Step 1 copies (\(0\), \(0\)), (\(6\), \(4\)) of F-list \(j-1\) to F-list \(j\). In Step 2, at \(en=(0,0)\) of F-list \(j-1\), \(d=5\), \(tp=9>\) TP = \(6\) (add new e-node (\(9\), \(5\))). At \(en=(6,4)\) of F-list \(j-1\), \(d=4+5=9\), \(tp=6+9=15>\) TP = \(6\) (add new e-node (\(15\), \(9\))). At \(en=(10\), \(12)\), \(d=17\), \(tp=19>\) TP = \(10\) (add new e-node (\(19\), \(17\))).