## 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 c} \hline \hline \multirow{2}{*}{\(n\leq 10\),000} & \multirow{2}{*}{**Optimal**} & \multicolumn{2}{c}{**mDPT-L**} & \multicolumn{2}{c}{**mDPT-L + LS**} & \multicolumn{2}{c}{**mDPT-L + mGH\({}^{+}\)**} & \multicolumn{2}{c}{**mGH\({}^{+}\) + LS**} \\  & & O(\(m^{2}\)[\(n^{2}\), \(n\)C]) & **Filter O(\(m^{2}\))** & **Filter O(\(mm\))** & **O(\(mm\))** & **O(\(m^{2}\))** \\ \hline \hline \multirow{2}{*}{\(m\):\(n\)} & \multicolumn{2}{c}{\(m!\)} & \(m!\) & \(m!\) & \(m!\) & \(m!\) & \(m!\) \\ \hline
3:51 & **1318** & 1318 & 1317 & 1317 & 1315 & 1315 \\
3:73 & **1727** & 1727 & 1725 & 1725 & 1725 & 1725 \\
4:33 & **752** & 752 & 747 & 747 & 747 & 747 \\
4:49 & **1264** & 1264 & 1263 & 1263 & 1254 & 1254 \\
4:50 & **1137** & 1137 & 1136 & 1136 & 1136 & 1136 \\
4:65 & **1565** & 1565 & 1563 & 1563 & 1563 & 1563 \\ \hline \hline \multirow{2}{*}{\(m\):\(n\)} & \multicolumn{2}{c}{Best} & 9 \(m\) & 9 & 9 & 9 \(m\) \\ \hline
5:89 & **2366** & 2366 & 2365 & 2365 & 2359 & 2359 \\
7:77 & **1834** & 1834 & 1833 & 1833 & 1829 & 1830 \\
7:138 & **3263** & 3263 & 3262 & 3262 & 3256 & 3256 \\
7:148 & **3780** & 3780 & 3799 & 3799 & 3773 & 3777 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: Results (total profits) of irregular datasets (\(m=3\)–\(7\), \(n\leq 10\),000). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\(m\)} & \multirow{2}{*}{**Optimal**} & \multicolumn{2}{c}{**mDPT-L**} & \multicolumn{2}{c}{**mDPT-L + LS**} & \multicolumn{2}{c}{**mDPT-L +**} & \multicolumn{2}{c}{**mGH\({}^{+}\) + LS**} \\  & & O(\(m^{2}\)[\(n^{2}\), \(n\)C]) & **Filter O(\(m^{2}\))** & **Filter O(\(mm\))** & **O(\(mm\))** & **O(\(m^{2}\))** \\ \hline \hline \multirow{2}{*}{\(C_{i}\)\(\pm\) 10} & \multicolumn{2}{c}{Best} & 9 \(\times\) 9 & 9 & 9 & 9 \(m\) \\ \hline
40 & **53,669** & 53,669 & 53,669 & 53,669 & 53,494 & 53,520 \\
50 & **54,803** & 54,803 & 54,803 & 54,803 & 54,538 & 54,655 \\
60 & **58,614** & 58,614 & 58,614 & 58,614 & 58,425 & 58,450 \\
70 & **64,018** & 64,018 & 64,018 & 64,018 & 63,689 & 63,784 \\ \hline \hline \multirow{2}{*}{\(C_{i}\)\(\pm\) 20} & \multicolumn{2}{c}{Best} & 9 \(\times\) 9 & 9 & 9 & 9 \(m\) \\ \hline
40 & **85,380** & 85,380 & 85,380 & 85,380 & 85,203 & 85,286 \\
50 & **100,859** & 100,859 & 100,859 & 100,859 & 100,0683 & 100,724 \\
60 & **118,729** & 118,729 & 118,729 & 118,729 & 118,525 & 118,616 \\
70 & **138,195** & 138,195 & 138,195 & 137,963 & 138,038 \\
80 & **158,983** & 158,983 & 158,983 & 158,722 & 158,857 \\
90 & **180,054** & 180,054 & 180,054 & 180,054 & 179,873 & 179,981 \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Results (total profits) of datasets (\(C\pm\) 10, 20), \(n=9000\) (\(m=40\)–90). However, it is not the problem in our robust unbiased filtering since all uncertain objects (\(n^{\prime}<300\)) were considered by the exact DPT-List with 99% optimal precision. In our initial observation and analysis, for \(m=2\) (\(n\leq\) 10,000), the mDPT-List + filtering (\(m!\) orders) in Table 5 yielded 100% optimal solutions. For \(m=3\), 4 (\(n\leq\) 10,000), our approach (\(m!\) orders) in Tables 6 and 7 yielded 99.9% optimal solutions. Next, we found that (for the irregular datasets) the top nine orders were not sufficient to find the optimal solutions \(\geq\)99%, especially \(m\geq 5\). Then, we investigated the effect of the LS of the top nine orders (see Column 4 in Tables 8-10). Moreover, Tables 10 and 11 report the irregular datasets found during the execution of each dataset (\(n\leq\) 10,000), where any dataset is called \"irregular\" when the top nine orders could not find the optimal solution. For \(m\geq 5\), we performed an intensive study and experiment to observe each of \(n\leq\) 10,000 (\(m\leq 100\)) and found that a number of irregular datasets increased when \(m\) increased (see Column 6 in Table 11). Hence, the exact-fit (best) knapsack order is applied to solve this problem.