## 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
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(m\) & **All Orders** & **Exact-Fit/Best** & **Top (9)** & **Partial LS** & **Full LS** \\
**Knapsacks** & **(mt)** & **(mt(m + 1)/2)** & **Orders** & **Min (9 m, 9 \(\times\) 9)** & **(9 m)** \\ \hline
5 & 120 & 15 & 9 & 45 & 45 \\
6 & 720 & 21 & 9 & 54 & 54 \\
7 & 5040 & 28 & 9 & 63 & 63 \\
8 & 40,320 & 36 & 9 & 72 & 72 \\
9 & 326,880 & 45 & 9 & 81 & 81 \\
10 & 3,268,800 & 55 & 9 & 81 & 90 \\
20 & 20! & 210 & 9 & 81 & 180 \\
50 & 50! & 1275 & 9 & 81 & 450 \\
100 & 100! & 5050 & 9 & 81 & 900 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: All possible (\(m!\)) knapsack orders and the proposed effective orders for the \(0/1\)-mKP. Figure 18: An example of increasing \(C_{i}\) (an effective knapsack order) for the \(0/1\)-mKP. \(0/1\)-mKP. Initially, all objects are classified (into four groups) by dynamic weighting (_dw_), integrated from three effective ranks (\(P/W\), \(P\), \(W\)); see Figure 19a, where two parameters (\(\alpha\), \(\beta\))) were defined to handle special objects (called outliers) in unbiased filtering [1] for the \(0/1\)-KP with 95% optimal solutions. In this study, to achieve 99% optimal solutions for the \(0/1\)-mKP, the (\(\gamma\), \(\alpha\), \(\beta\)) parameters are introduced by studying all datasets (i.e., most datasets are regular (\(\approx\)90%) and irregular datasets are \(\approx\)10%). In our robust unbiased filtering, the (\(\gamma\), \(\alpha\), \(\beta\), \(U\)) parameters are determined in Equations (10)-(14), where the critical objects are in low rank in Group 1 (\(\gamma\)) and Group 2 (\(\alpha\)) and in top rank in Group 4 (\(\beta\)), and most uncertain objects (\(U\)) are in Group 3. Figure 19a shows that some objects (around the critical points in the three ranks (\(P/W\), \(P\), or \(W\))) are the critical objects (\(\gamma\), \(\alpha\), \(\beta\)). All uncertain/critical objects (\(n^{\prime}\)! \(<\) 300) can be solved by the DPT-List\({}_{\text{TSR}}\) algorithm in O(\(n+C^{\prime}\)). Figure 19b shows the idea of 99% optimal precision (due to our robust unbiased filtering) in each knapsack of the \(0/1\)-mKP; see in the observed results (in Section 6). ## 6 Experimental Results

Experiments were conducted to evaluate the DPT-List\({}_{\text{TSR}}\) algorithm and robust unbiased filtering for the \(0/1\)-KP (Section 6.1) to ensure at least 99% optimal precision (in each knapsack) before applying to the \(0/1\)-mKP (Sections 6.2 and 6.3) by the multi-DPT-List\({}_{\text{TSR}}\) algorithm (the best knapsack-order for \(m\) knapsacks) and robust unbiased filtering. ### Results of the DPT-List\({}_{\text{TSR}}\) (One Knapsack) and Robust Unbiased Filtering

For solving the \(0/1\)-KP, we generated a variety of random datasets (dynamic seeds) with a number of uniform distributions to obtain the profits and weights of \(n\) objects (\(n\leq 10\),000). The experiment was conducted to evaluate the performance of robust unbiased filtering. In the experimental results, our DPT-List\({}_{\text{TSR}}\) + robust unbiased filtering could find the exact solutions in each of the datasets (\(n\leq 10\),000), while there were 223 (of 10,000) datasets for which the recent TS\({}_{\text{Reduction}}\) + unbiased filtering [1] could not find the optimal solutions. Table 2 shows the empirical results of the first 23 of 223 special datasets (or irregular datasets), \(n\) = 12, 14, 21, 26, 39,..., 385 (observed on \(n\) = 5, 6, 7,..., 9999, 10,000). Figure 19: High (optimal) precision of robust unbiased filtering for each \(K_{i}\) of \(0/1\)-mKP: (**a**) object classification and (**b**) robust unbiased filtering and DPT-List\({}_{\text{TSR}}\) for remaining \(n^{\prime}\) \(<\) 300. Table 3 presents the optimal performance of our DPT-List\({}_{\text{TSR}}\) + robust unbiased filtering for at least 99% optimal solutions (on \(n\)\(\leq\) 10,000) compared to our previous work [1].