## 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
For \(n\leq 500\) (in the critical datasets), the HyMKP model yielded 99.9% optimal solutions by the partial BnB (MULKNAP) program in \(\tau\) secs. Thus, for \(n\leq 500\) we can adopt that MULKNAP program in our approach for achieving 99.9% optimal solutions. Finally, after achieving the good performance (99% optimal solutions) of our multi-DPT-List\({}_{\text{TSR}}\) + robust filtering in the efficient time O(\(m^{2}n\)), we can improve the time complexity to O(\(mn\)) in parallel (by using \(p=m\) processors). Moreover, to handle the critical datasets in parallel, we can achieve the global best result in parallel (by \(p=m\) processors), such as Column 3 (in Table 13), by combining the local best result of the parallel multi-DPT-List\({}_{\text{TSR}}\) in O(\(m[n^{2},\,nC]\)) in Column 4 and the local best result of the parallel multi-DPT-List\({}_{\text{TSR}}\) + robust filtering in O(\(mn\)) in Column 6 for the best of the best results (in Column 3) in O(\(m[n^{2},\,nC]\)), which is efficient, especially in average \(\approx\) O(\(mn^{3}\)) if \(C=\max(C_{i})\leq n^{2}\). In practical 0/1-mKP applications (for large \(n\)), if the fast computing time is the most important factor (in the regular and irregular datasets), our multi-DPT-List + robust filtering in O(\(m^{2}n\)) or O(\(mn\)) in parallel (\(p=m\)) with 99% optimal solutions is good enough. However, \begin{table}
\begin{tabular}{c c c} \hline \hline  & **For Regular and Irregular Datasets (\(n\leq\) 10,000, \(m\leq\) 100)** & \\ \hline \multirow{2}{*}{\begin{tabular}{c} **Exact +** \\ **Filtering** \\ \end{tabular} } & **Our multi-DPT-List + robust filtering (the exact-fit best order)** & \\  & could find most optimal solutions (\(\geq\)99\%) in efficient response time & **O(\(m^{2}n\))** \\  & (\(<\)1 s per \(n\)); see confirmed results in Tables 5–12. & \\ \hline \multirow{4}{*}{\
\begin{tabular}{c} **Exact** \\ **Filtering** \\ \end{tabular} } & **Mathematical HyMKP**[34] can execute in \(\tau\) secs. with Algorithm 6 & \\  & (reflect multi-graph MKP with decreasing \(n\) weights (\(w_{j}\))) like the & \\  & basic DP for each of \(m\) knapsacks. That initial solution can be & **O(\(mn\)C)** \\  & improved by the knapsack decomposition in \(\
u\) iterations to find the & \\  & optimal solution (\(n\leq 500\)) in \(\tau\) secs. However, no available results for & \\  & \(n>500\) in that study. & \\ \hline \multirow{4}{*}{\begin{tabular}{c} **Heuristic** \\ **Heuristic** \\ \end{tabular} } & **Multi-GH\({}^{+}\) (Latin squares of top nine orders)** could find good & \\  & solutions in efficient time (\(<\) 1 s) but they are not optimal (see the last & \\  & column results in Tables 5–10 and Table 12). Note: LSs of top 9 orders & \\  & could emulate 9 \(m\) iterations/evolutions in the GA/swarm & \\  & optimization with good results (near optimal in each knapsack for & \\  & small \(m\)). & \\ \hline \hline \multirow{4}{*}{\begin{tabular}{c} **Exact** \\ **Filtering** \\ \end{tabular} } & **For critical and special benchmark datasets (\(n\leq\) 500)**[34] & \\ \hline \multirow{2}{*}{\
\begin{tabular}{c} **Exact** \\ **Filtering** \\ \end{tabular} } & **Partial BnB (in HyMKP)**[34]: The existing BnB (MULKNAP & \\  & program) could find most optimal solutions (\(\geq\)99.9%) in \(\tau\) secs for & **O(\((n+1)^{m}\))** \\  & \(n\leq 500\). & \\ \hline \multirow{4}{*}{
\begin{tabular}{c} **Exact +** \\ **Filtering** \\ \end{tabular} } & **Our multi-DPT-List + robust filtering (the best order):** For critical & \\  & datasets in 0/1-mKP applications, we can adopt the MULKNAP & \\  & program [34] for \(n\leq 500\) in our approach to achieve 99.9% optimal & **O(\(m^{2}n\))** \\  & solutions. For \(n>500\) we can apply our efficient multi-DPT-List + filtering in efficient time. & \\ \hline \hline \end{tabular}
\end{table} 
Table 14: Comparison of our multi-DPT-List + robust filtering and the mathematical HyMKP.