## 4 0/1-mKP Solving by Multi-DPT-List\({}_{\text{TSR}}\) Plus Unbiased Filtering in Efficient Time
### Efficient Multi-DPT-List\({}_{\text{TSR}}\) Algorithm for Solving 0/1-mKP
#### 4.1.2 The Exact-Fit (Best) Knapsack Order for Regular and Irregular Datasets
Second, for \(en=(6,4)\), a new e-node (\(6+9,4+5)=(15,9\)) is added to F-list \(j\). Third, for \(en=(10,12)\), this remaining e-node is not inherited, whereas a new e-node (\(10+9,12+5)=(19,17)\) is added to F-list \(j\). Note: Function \"inherit remaining e-node\" (in Algorithm 7: Line 6) is presented in Figure (b)b; see the complex inherited results in Figure 6 (\(n=15\)). Finally, our X-tracking (Algorithm 8) can find \(solx[n]\) from the original e-nodes (on the B-lists in Figure 7), similar to the basic DP (on the 2D-array). Figure 16: An example of the correct F-list \(j\) construction (\(n=5\) in Figure 5): (a) F-list \(j=1\) (add a new e-node to tail of F-list \(j\)) and (b) F-list \(j=3\) (add each of three new e-nodes to tail of F-list \(j\)). ### Complexity Analysis of the DPT-List\({}_{\text{TSR}}\) Algorithm

The time complexity of our DPT-List\({}_{\text{TSR}}\) algorithm for solving the 0/1-KP is O([\(n^{2}\), \(n\)C]), according to the efficient reduction of computing time and using space; see Figure 17 (our efficient time-space reduction). Our time complexity depends on the number of e-nodes of the (temporary) F-list \(j\) for all \(j\) = 0, 1, 2, 3,..., \(n-1\), where \(\mid\) F-list \(j\mid\)\(\leq\) 2 \(\mid\) F-list \(j-1\)\(\mid\); see a simple example (\(n\) = 5) in Figure 5. The (initial) F-list \(j\) contains one e-node (\(tp\), \(d\)) = (0, 0). For object \(j\) = 0, there are at most two e-nodes (\(\leq\)2 nodes). For object \(j\) = 1 (\(\leq\) 4 nodes) and for any \(j\) (\(\leq\) 2 \(\times\) 2\({}^{j-1}\) nodes), the time complexity of our DPT-List\({}_{\text{TSR}}\) algorithm can be the best, average, or worst cases, depending on the datasets. Figure 5 displays one of the best cases (\(n\) = 5, \(C\) = 18, e-nodes = 19, and original e-nodes = 7, reduced from \(n\)C = 90 elements). Thus, in this analysis, the best and worst cases can be derived as follows:

* Best case: Total steps (\(n\) objects (\(j\) = 0 to \(n-1\))) are approximately \(1+2+4+\ldots+2\)(\(j\) + 1) + \(\ldots+2n\)\(\approx\)\(n(n+1)\) = O(\(n^{2}\)). * Worst case (rarely occurs): Total steps are approximately \(1+2+(\leq\)4) + \((\leq\)8) + \(\ldots+(\leq\)2\(\times\)2\()\) + \(\ldots+(\approx\)\(n\)\(\times\)\(C/2)\) = O(\(n\)C). The worst case (the e-nodes of F-list\({}_{n-1}\) = \(\mid\) F-list\({}_{n-1}\)\(\mid\)\(\approx\) C) hardly occurs due to some remaining e-nodes of F-list \(j-1\) are not inherited to F-list \(j\) (see a clarified example in Figure 16b) and no additional new e-nodes in F-list \(j\) when considering some (worst) objects \(j\) (such as large \(w_{j}\) or tiny profit \(p_{j}\)) by two conditions: 1. _node.tp + \(p_{j}\) < tp[\(d\)]_ (no improved \(tp\)) and 2. _node.d + \(w_{j}\) > C_ (at \(d\) + \(w_{j}\), object \(j\) cannot be packed in the knapsack), such as no additional new e-node for object \(j\) = 4 (in Figure 5). Figure 6 shows an example of a regular/average case (\(n\) = 15, \(C\) = 40, \(n\)C = 600, e-nodes = 223, and original e-nodes = 103). The time complexity of the average case arises in most datasets (\(\approx\)(best + worst)/2 \(<\)\(n\)C/2). Since a weight \(w_{j}\) of object \(j\) can be \(1\leq w_{j}\) < \(C\), the average \(w_{j}\) is approximately \(C/n\). For \(w_{j}\)\(\geq\)\(C/n\), usually no e-node is added (because of the condition _node.d + \(w_{j}\) > C_). For \(m\) knapsacks, the time complexity of our multi-DPT-list\({}_{\text{TSR}}\) algorithm for solving the 0/1-mKP is O(\(m[n^{2}\), \(n\)C]) with any effective knapsack order (including top nine orders) and O(\(m^{2}[n^{2}\), \(n\)C]) for the exact-fit (best) order in \(m(m+1)/2\) steps; see Section 5.3. For space complexity, Figure 17 illustrates our three steps of space reduction: 1. e-nodes (\(<\)\(n\)C), 2. original e-nodes, and 3. tight bound of e-nodes; see Figure 5 (\(n\) = 5, \(C\) = 18) and Figure 7b (\(n\) = 15, \(C\) = 40).