## 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
In this experiment, there exist irregular datasets \(\approx\)10% (from all 10,000 random datasets), where unbiased filtering (in TS\({}_{\text{Reduction}}\)) [1] could handle \(\approx\)5% and our robust unbiased filtering (in DPT-List\({}_{\text{TSR}}\)) could handle \(\approx\)9.9%. Table 4 displays our space reduction, observed on \(n\)\(\leq\) 3000 (with runtime \(<\) 1 min per \(n\)). Our F-reduction can save space 69-92%, and our B-reduction can save space 84-93%. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{\(n\)} & \multicolumn{2}{c}{\(n\)\(\times\)\(C\)} & \multicolumn{2}{c}{**e-Nodes**} & \multicolumn{2}{c}{**Original e-Nodes**} & \multicolumn{2}{c}{**Tight-Bound e-Nodes**} \\  & **(Full Space)** & **(1. Initial Reduction)** & **(2. F-reduction)** & **(3. B-Reduction)** & **(3. B-Reduction)** \\ \hline
5 & 90 & 13 & 86\% & 7 & 92\% & 6 & 93\% \\
15 & 600 & 223 & 63\% & 103 & 83\% & 50 & 92\% \\
50 & 17,450 & 6559 & 62\% & 2465 & 86\% & 1917 & 89\% \\
100 & 69,900 & 35,852 & 49\% & 15,263 & 78\% & 10,849 & 84\% \\
200 & 239,800 & 150,518 & 37\% & 66,883 & 72\% & 35,932 & 85\% \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Performance (percentage) of space reduction by the DPT-List\({}_{\text{TSR}}\) (\(n\)\(\leq\) 3000). \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multicolumn{8}{c}{**Total Weight (\(soltr\))**} & \multicolumn{4}{c}{**Total Profit (\(soltr\))**} \\ \hline \multirow{2}{*}{\(n\)} & \multirow{2}{*}{\(C\)} & \multicolumn{2}{c}{\( \begin{array}{c}\text{DPT-List}\\ \text{(Opt.)}\end{array} \)} & \multicolumn{2}{c}{\( \begin{array}{c}\text{TSR + uFilter}\\ \text{(1]}\end{array} \)} & \multicolumn{2}{c}{\( \begin{array}{c}\text{DPT-List}\\ \text{(Opt.)}\end{array} \)} & \multicolumn{2}{c}{\( \begin{array}{c}\text{DPT-List}\\ \text{(Opt.)}\end{array} \)} & \multicolumn{2}{c}{\(\begin{array}{c}\text{DPT+}\\



Results of the Multi-DPT-List\({}_{\text{TSR}}\) (\(m\) Kuapsacks) and Robust Unbiased Filtering

For solving the 0/1-mKP, the optimal performance of our multi-DPT-List\({}_{\text{TSR}}\) algorithm with the proper (knapsack) orders (i.e., top nine orders, Latin squares, the exact-fit (best) order) was evaluated by comparison to the optimal solutions. In practice, the fast response time of our multi-DPT-List\({}_{\text{TSR}}\) with robust unbiased filtering was observed, while retaining the high performance. In this experiment, a number of random datasets were generated for \(n\) (\(\leq\)10,000) objects and \(m\) (\(\leq\)100) knapsacks with a variation of capacities (i.e., \(C_{i}\pm 10\), \(C_{i}\pm 15\), \(C_{i}\pm 20\), etc.). In addition, the benchmark datasets [34] were observed and the empirical results were compared to the optimal solutions. In performance (total profit) evaluation, we focus on the investigation of 1. the exact-fit best (knapsack) order in our multi-DPT-List algorithm (for 99% optimal solutions in theory) and 2. the robust unbiased filtering (in polynomial time) to confirm 99% optimal solutions. We implemented our multi-DPT-List (the exact-fit best order) and the fast multi-DPT-List + robust filtering compared to the optimal solutions. For the practical polynomial-time evaluation, the fast response time of our multi-DPT-List + robust filtering was compared to the quick multi-GH\({}^{+}\) (a well-known heuristic algorithm). For the performance comparison, the (known) optimal solutions of the 0/1-mKP (in Column 2 of Tables 5-10) can be computed by using a large knapsack (\(C^{*}=\sum_{i=1}^{m}\ C_{i}\)) by the exact DP or our DPT-List in the (regular and irregular) datasets. The implemented programs of three main approaches (in this experiment) are