## 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
Our (fast and efficient) unbiased filtering can select the outstanding objects (from \(n\) objects), and only uncertain objects (\(n^{\prime}<300\)) are considered by the DPT-List\({}_{\text{TSR}}\) algorithm (in each knapsack). For the 0/1-mKP, the parameter (\(\gamma\), \(\alpha\), \(\beta\))-setting (in Equations (10)-(14)) was our key contribution to retain 99% optimal precision, as in our previous work (Algorithm 4) [1]. Usually, the critical and uncertain objects (\(\gamma\), \(\alpha\), and \(\beta\)) could not be easily found. In this study, we performed the experiment on a variety of datasets (including the critical datasets) to classify objects into four groups (see Figure 12) before performing the efficient unbiased filtering. Variables (\(\gamma\), \(\alpha\)) refer to some critical objects (in Groups 1-2), another variable \(\beta\) refers to other critical objects (in Group 4), and most uncertain objects (\(U\)) are in Group 3. Figure 11: (a) The exact-fit policy for the best knapsack order and (b) an example of \(n=33\), \(m=5\), \(C=\) (66,26,80,96,70) to find the best order (2,4,1,5,3) in \(m(m+1)/2=15\) steps and the optimal result (726). Figure 14: An example of robust unbiased filtering before applying DPT-List\({}_{\text{TSR}}\) on \(n^{\prime}\) in \(K_{1}\) and \(K_{2}\). Figure 15: (**a**) The exact-fit policy plus efficient filtering for the best knapsack order and (**b**) an example of \(n=33\), \(m=5\), \(C=(66,26,80,96,70)\) to find the best order (2, 4, 1, 5, 3) in \(m(m+1)/2=15\) steps and the optimal result (726) by the multi-DPT-List\({}_{\text{TSR}}\) + robust unbiased filtering. ## 5 Analysis of Proposed Algorithms

The correctness of the DPT-List\({}_{\text{TSR}}\) algorithm for solving the 0/1-KP was proven in Section 5.1 and its complexity was analyzed in Section 5.2. For solving the 0/1-mKP, the high (optimal) precision (as \(m!\) orders) of the exact-fit (best) knapsack order was presented in Section 5.3. Finally, the 99% optimal precision of the robust unbiased filtering for solving the 0/1-KP and the 0/1-mKP were analyzed in Section 5.4. ### Correctness of the DPT-List\({}_{\text{TSR}}\) Algorithm

The DPT-List\({}_{\text{TSR}}\) algorithm (in Section 3) was designed to solve the 0/1-KP in O([\(n^{2}\), \(nC\)]) on the efficient lists, which can find the optimal solutions as the best DP (Algorithm 1: O(\(nC\)) on a 2D-array (\(n\times C\))) before being applied in each of \(m\) knapsacks. Our DPT-List\({}_{\text{TSR}}\) algorithm can reduce not only the redundant computing time but also the space consumption (of the basic DP: Algorithm 1) while retaining the correctness. Our focus is the DP transformation of the 2D array (\(n\)xC) to the efficient lists of e-nodes. Our preprocessing (Algorithm 7) employs two (temporary) F-lists (of objects \(j-1\) and \(j\)) to inherit all worth e-nodes (of objects 0 to \(j-1\)) and compute new e-nodes (improved _tp value_s by the current object \(j\)) before saving only the original e-nodes in B-list \(j\). To clarify our correct transformation, Figure 16 shows the construction of e-nodes (of F-lists \(j\)) in Figure 5 (\(n=5\)). For object \(j=1\) (\(p_{1}=10\), \(w_{1}=15\)), Figure (a)a displays the F-list \(j\) construction. After the initial copy of two e-nodes (\(cn=(p,d)=(0,0)\) and \((4,8)\)) from F-list \(j-1\) (while \(cn.tp<p_{1}\) and \(cn.d<w_{1}\)) to F-list \(j\), the rest of F-list \(j\) is fulfilled. For the first e-node \(en=(0,0)\) of F-list \(j-1\), a new e-node (\(10,15\)) with \(d=15<\mathcal{C}\) and \(tp=10>\text{TP}=4\) is added to the end of F-list \(j\). For the next \(cn=(4,8)\), compute \(d=8+15=23>\mathcal{C}\) (no new e-node is added). For object \(j=3\) (\(p_{3}=9\), \(w_{3}=5\)), Figure (b)b shows the F-list \(j\) construction in three steps. After the initial copy of two e-nodes (\(cn=(0,0)\) and \((6,4)\)) from F-list \(j-1\) (while \(cn.tp<p_{3}\) and \(cn.d<w_{3}\)) to F-list \(j\), the rest of F-list \(j\) is fulfilled. For \(en=(0,0)\), a new e-node (\(9,5\)) is added to F-list \(j\).