## 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
After performing the intensive study and comparison (on large \(n\leq\) 10,000), we found that for the irregular datasets, our mDPT-List + robust unbiased filtering (the exact-fit (best) order in O(\(m^{2}n\))) could find at least 99% optimal solutions as those of the original mDPT-List (O(\(m^{2}[n^{2}\),\(n\)C])); see a report of observed frequency of nonoptimal solutions (0%) of our approach in Table 11 (Column 4). Finally, we performed an extra experiment to evaluate the performance of our mDPT-List on the benchmark datasets [34] available at [[http://or.dei.unibo.it/library](http://or.dei.unibo.it/library)]([http://or.dei.unibo.it/library](http://or.dei.unibo.it/library)) (accessed on 13 June 2020). Tables 12 and 13 show the empirical results of our mDPT-List (the best knapsack order in O(\(m^{2}[n^{2},\)\(nC]\))) and our fast mDPT-List + robust filtering (the best knapsack order in O(\(m^{2}n\))), compared to the regular mDP (O(\(m^{2}n\)C)) and the optimal solutions. For (\(n\):\(m=\) 100:10) 10 datasets [34], the results (in Table 12) showed that our mDPT-List (without/with filtering (the best order, LS orders, top nine orders)) could find the optimal solutions (Columns 4-7), while the results (Column 8) of the quick mGH\({}^{+}\) (9 \(m\) orders in 9 \(m\) iterations) were not optimal. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \(n\leq\) 10,000 & **mDPT-L: O(\(m^{2}[n^{2}\), \(n\)C])** & \multicolumn{3}{c}{**mDPT-L + Filtering: O(\(m^{2}n\))**} \\ \hline \(m\) & **Best** & **9 \(m\) (LS)** & **Best** & **9 \(m\) (LS)** & **Top 9** \\ \hline
5 & 0 & 0 & 0 & 1 & 2 \\
7 & 0 & 1 & 0 & 3 & 6 \\
8–14 & 0 & 0 & 0 & 2 & 1.6 (ave. per \(m\)) \\
15–19 & 0 & 0 & 0 & 0 & 1.6 (ave. per \(m\)) \\
20–24 & 0 & 0 & 0 & 0 & 2.6 (ave. per \(m\)) \\
25–29 & 0 & 0 & 0 & 0 & 4.8 (ave. per \(m\)) \\
30–34 & 0 & 0 & 0 & 0 & 5.4 (ave. per \(m\)) \\
35–39 & 0 & 0 & 0 & 0 & 13.8 (ave. per \(m\)) \\
40–44 & 0 & 0 & 0 & 0 & 31.4 (ave. per \(m\)) \\
45–49 & 0 & 0 & 0 & 0 & 34.8 (ave. per \(m\)) \\
50–54 & 0 & 0 & 0 & 0 & 69.2 (ave. per \(m\)) \\ \hline \hline \end{tabular} Note: When observing the irregular datasets, using top 9 orders (Column 6) in our mDPT-List + filtering could not find the optimal solutions in approximate 69 datasets (in average) of \(n\leq\) 10,000, \(m=54\) in the (random) regular and irregular datasets, while using the best order (Column 4) could find all optimal solutions.

\end{table} 
Table 11: Observed frequency of nonoptimal solutions (in \(n\leq\) 10,000 per \(m\)), \(m=5\), 6, 7,..., 53, 54. For (\(n\):\(m\) = 200:20, 300:30, 500:50) 20 datasets [34], most optimal solutions of these critical datasets were unknown (see Table 13) since the DP-packing in one large knapsack (\(\text{C}^{\text{s}}=\sum_{i=1}^{m}\text{C}_{i}\)) may be overpacking. Figure 20a shows an example of overpacking, when some objects in the critical datasets (such as some valuable objects \(j\) (high \(p_{j}/w_{j}\)) but large \(w_{j}\)) cannot be packed in any knapsack \(i\) with capacity \(C_{i}\), except in the extra space of one knapsack of large capacity \(\text{C}^{\text{s}}\). In these critical datasets, our mDPT-List with the best order (in Columns 5 and 6) yielded good results, which were close to or equal to the optimal solutions and outperformed those of LSs (\(9m\)) of top nine orders (in Columns 7-8). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multicolumn{1}{c}{**Research Approach**} & \multicolumn{2}{c}{**Exact**} & \multicolumn{2}{c}{**Exact + Filtering**} & \multicolumn{1}{c}{**Heuristic**} \\ \hline  & **Over** & & & & & \\  & **Packing *** & & & & & \\  & **O(\(m^{2}\)[\(n^{2}\), \(n\)C])** & & & & & \\ \hline \multirow{2}{*}{\(n\):\(m\)} & **Optimal** & **Best of** & **Best** & & & \\  & **this study** & **+extra** & **Best** & **9 \(m\)** & **9 \(m\)** \\ \hline



795 & 135,795 & **135,796** & 135,736 & 134,793 \\ \hline \hline \end{tabular} Note: The symbol * (in Column 2) means that the (extra) solution may be overpacking.

\end{table}