## 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\)} & \multirow{2}{*}{\(n\times C\)**} & \multicolumn{2}{c}{**e-Nodes**} & \multicolumn{2}{c}{**Original e-Nodes**} & \multicolumn{2}{c}{**Tight-Bound e-Nodes**} \\  & & **(Full Space)** & **(I. Initial Reduction)** & **(2. F-reduction)** & **(B. B-Reduction)** \\ \hline
500 & 1,250,000 & 915,303 & 27\% & 374,729 & 70\% & 173,786 & 86\% \\
1000 & 5,000,000 & 3,832,827 & 23\% & 1,566,414 & 69\% & 692,691 & 86\% \\
1500 & 11,250,000 & 8,669,932 & 23\% & 3,364,525 & 70\% & 1,581,133 & 86\% \\
2000 & 11,998,000 & 10,322,643 & 14\% & 3,293,641 & 73\% & 1,115,040 & 91\% \\
2500 & 18,747,500 & 16,071,768 & 14\% & 5,338,435 & 72\% & 1,752,052 & 91\% \\
3000 & 26,997,000 & 23,225,460 & 14\% & 7,497,627 & 72\% & 2,620,552 & 90\% \\ \hline \hline \end{tabular}
\end{table} 
Table 4: _Cont._ \begin{table}
\begin{tabular}{c c c c} \hline \hline Exact & 1.1 Multi-DPT-List (exact-fit best order) & O(\(m^{2}\)[\(n^{2}\),\(nC\)]) \\ \hline Exact + Filtering & 2.1 Fast multi-DPT-List + filtering (exact-fit best order) & O(\(m^{2}\)) \\  & 2.2 Fast multi-DPT-List + filtering (top 9 orders + partial LSs) & O(\(mn\)) \\  & 2.3 Fast multi-DPT-List + filtering (top 9 orders) & O(\(mn\)) \\ \hline Heuristic & 3.1 Quick multi-GH (\(P/W\) rank) (top 9 orders) & O(\(mn\)) \\  & 3.2 Improved multi-GH\({}^{+}\) (\(P/W\) rank) (top 9 orders) & O(\(mn\)) \\  & 3.3 Improved multi-GH\({}^{+}\) (\(P/W\) rank) (top 9 + full LS orders) & O(\(m^{2}\)) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Results (total profits) of datasets with capacities \(C\pm 10\) (\(m=2\)). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\(m=3\)} & \multirow{2}{*}{**Optimal**} & \multicolumn{2}{c}{**mDPT-L**} & **mDPT-L + Filter** & **mGH** & **mGH\({}^{+}\)** \\  & & \(\textit{m!}\)** O(\(\textit{m}\)\(\textit{n}^{2}\), \(\textit{nC}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** \\ \hline \(n\) & & \(\textit{m!}=6\) & \(\textit{m!}=6\) & \(\textit{m!}=6\) & \(\textit{m!}=6\) \\ \hline
15 & **327** & 327 & 327 & 320 & 322 \\
20 & **466** & 466 & 466 & 454 & 466 \\
30 & **840** & 840 & 840 & 829 & 839 \\
40 & **1103** & 1103 & 1103 & 1090 & 1099 \\
50 & **1067** & 1067 & 1067 & 1031 & 1062 \\
100 & **2427** & 2427 & 2427 & 2390 & 2426 \\
200 & **3949** & 3949 & 3949 & 3908 & 3943 \\
500 & **9150** & 9150 & 9150 & 9133 & 9148 \\
1000 & **18,112** & 18,112 & 18,112 & 18,088 & 18,110 \\
2000 & **25,547** & 25,547 & 25,547 & 25,524 & 25,544 \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Results (total profits) of datasets with capacities \(C\pm 15\) (\(m=3\)). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{\(m=4\)} & \multirow{2}{*}{**Optimal**} & \multicolumn{2}{c}{**mDPT-L**} & **mDPT-L + Filter** & **mGH** & **mGH\({}^{+}\)** \\  & & \(\textit{m!}\)** O(\(\textit{m}\)\(\textit{n}^{2}\), \(\textit{nC}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** & \(\textit{m!}\)** O(\(\textit{mm}\))** \\ \hline \(n\) & & \(\textit{m!}=24\) & \(\textit{m!}=24\) & \(\textit{m!}=24\) & \(\textit{m!}=24\) \\ \hline
20 & **495** & 495 & 495 & 490 & 490 \\
30 & **884** & 884 & 884 & 884 & 884 \\
40 & **1200** & 1200 & 1200 & 1187 & 1192 \\
50 & **1137** & 1137 & 1136 & 1121 & 1136 \\
60 & **1504** & 1504 & 1504 & 1472 & 1499 \\
100 & **2548** & 2548 & 2548 & 2534 & 2546 \\
200 & **4098** & 4098 & 4098 & 4071 & 4088 \\
500 & **9318** & 9318 & 9318 & 9297 & 9314 \\
1000 & **18,284** & 18,284 & 18,284 & 18,249 & 18,280 \\
2000 & **25,760** & 25,760 & 25,760 & 25,735 & 25,752 \\
3000 & **38,941** & 38,941 & 38,941 & 38,899 & 38,930 \\ \hline \hline \end{tabular}
\end{table} 
Table 7: Results (total profits) of datasets with capacities \(C\pm 20\) (\(m=4\)).