## 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 \multirow{2}{*}{\(m\)} & \multirow{2}{*}{**Optimal**} & \multicolumn{2}{c}{**mDPT-L**} & **mDPT-L + LS** & **mDPT-L +** & **mGH\({}^{+}\)** & **mGH\({}^{+}\)** + LS** \\  & & \(\textbf{O(\textit{m}\)\(\textit{n}^{2}\)\(\textit{n}\)\(\textit{n}\)\(\textit{C}\))} & **Filter O(\(\textit{m}\)\(\textit{n}\)\(\textit{n}\))** & **Filter O(\(\textit{mm}\))** & **O(\(\textit{mm}\))** & **O(\(\textit{m}\)\(\textit{m}\)\(\textit{n}\))** \\ \hline \(n=1000\) & Best & 9 \(m\) & 9 & 9 & 9 \(m\) \\ \hline
6 & **18,541** & 18,541 & 18,541 & 18,541 & 18,535 & 18,535 \\
7 & **18,703** & 18,703 & 18,703 & 18,703 & 18,684 & 18,693 \\
8 & **18,889** & 18,889 & 18,889 & 18,889 & 18,879 & 18,884 \\
9 & **19,079** & 19,079 & 19,079 & 19,079 & 19,068 & 19,071 \\ \hline \hline \(n=2000\) & Best & 9 \(\times\) 9 & 9 & 9 & 9 \(m\) \\ \hline
12 & **27,769** & 27,769 & 27,769 & 27,769 & 27,742 & 27,753 \\
13 & **28,154** & 28,154 & 28,154 & 28,154 & 28,127 & 28,127 \\
14 & **28,547** & 28,547 & 28,547 & 28,547 & 28,498 & 28,517 \\
15 & **28,948** & 28,948 & 28,948 & 28,948 & 28,900 & 28,935 \\ \hline \hline \(n=5000\) & Best & 9 \(\times\) 9 & 9 & 9 & 9 \(m\) \\ \hline
20 & **54,736** & 54,736 & 54,736 & 54,736 & 54,680 & 54,695 \\
30 & **62,496** & 62,496 & 62,496 & 62,496 & 62,410 & 62,450 \\
40 & **72,417** & 72,417 & 72,417 & 72,417 & 72,323 & 72,331 \\
50 & **84,051** & 84,051 & 84,051 & 84,051 & 83,943 & 83,963 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Results (total profits) of datasets (\(C\pm 20\)), \(n=1000\)–5000 (\(m=6\)–50). First, we evaluated the performance of our mDPT-List and fast mDPT-List + filtering with \(m!\) orders (for small \(m=2,3,4\)), compared to the optimal solutions. For \(m\leq 4\), our approach can find the optimal solutions in most datasets; see Columns 3 and 4 in Tables 5-7. For \(m>4\), we investigated the effect of robust filtering plus the top nine effective orders and partial Latin squares (Columns 4 and 5 in Tables 8 and 9). For the regular datasets (\(n\leq 10\),000, \(m\leq 100\)), our mDPT-List + filtering (top nine orders) yielded 99% optimal solutions. Second, we aimed to compare among the fast polynomial-time algorithms (O(\(mn\)) - O(\(m^{2}\))) by observing the effect of the top nine effective orders; see Columns 4-7 in Tables 8 and 9. For \(m\leq 100\) and \(n\leq 10\),000, the results (total profits) of our mDPT-List + filtering (in Column 5) were compared to those of the quick mGH\({}^{+}\) (\(P/W\) rank) in Columns 6-7 (response time < 1 s). For the regular datasets, our fast mDPT-List + filtering (in Column 5) yielded most optimal solutions, while the results of the quick mGH\({}^{+}\) (in Column 6) and its improvement with LS of 9 \(m\) orders (in Column 7) were far from the optimal solutions, especially when using many knapsacks (\(m>10\)). Note: GH (\(P/W\) rank) is frequently used in many meta-heuristic algorithms (i.e., GA, swarm, etc.) for the good initial solutions to solve the 0/1-KP and GH\({}^{+}\) is used in unbiased filtering (1) (p. 199) and in robust unbiased filtering (in this study). In the comparison, we use the improved mGH\({}^{+}\) with the Latin squares of top nine orders (for 9 \(m\) orders/iterations to emulate the evolution process of GA/swarm optimization). For most datasets, the mGH\({}^{+}\) (9\(m\) orders) could not find the optimal solutions in each knapsack since it included uncertain object(s) in the solution.