## 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

Table 12: Results (total profits) of 10 benchmark datasets (\(n=100\), \(m=10\)). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multicolumn{1}{c}{**Research Approach**} & \multicolumn{2}{c}{**Exact**} & \multicolumn{2}{c}{**Exact + Filtering**} & \multicolumn{1}{c}{**Heuristic**} \\ \hline  & **mDP** & **mDPT-L** & **mDPT-L + Filter**: **O(\(m^{2}\)**\(n\)**)** & **mGH\({}^{*}\)** \\ \hline \(n\):\(m\) & **Optimal** & Best & Best & Best & 9 \(m\) & 9 & 9 \(m\) \\ \hline
100:10-1 & **26,797** & 26,797 & 26,797 & 26,797 & 26,797 & 26,763 \\
100:10-2 & **24,116** & 24,116 & 24,116 & 24,116 & 24,116 & 24,093 \\
100:10-3 & **25,828** & 25,828 & 25,828 & 25,828 & 25,828 & 25,812 \\



In our contribution, we focus on large \(n\). The fast mDPT-List + filtering (top nine orders) in O(\(mn\)) is good for the regular datasets with 99% optimal solutions (Tables 5-9 and 12). For the irregular datasets (Table 11), our fast mDPT-List (the best order) + filtering in O(\(m^{2}n\)) can find 99% optimal solutions similar to our original mDPT-List (the best order). Thus, for the regular and irregular datasets, our fast mDPT-List + filtering (the best order) is sufficient to achieve 99% optimal solutions in polynomial time O(\(m^{2}n\)). Moreover, for the critical/special benchmark datasets, we have intensively studied by the experiment (in Section 6.3) to improve the solutions (Column 4 in Table 13). ### Extra Experiment and Additional Improvement on Critical Datasets

To improve the results of the critical datasets (benchmark datasets [34]), we have to find all possible critical decisions, such as 1. nonunique Xs (in X-tracking (see an example in Figure 10) in Section 4.1.1) and 2. equal \(min(dFits)\) in more than one knapsacks (in the exact-fit (best) order (see an example in Figure 11) in Section 4.1.2) and provide the right policies to handle them. Clearly, if there is only one \(min(dFit_{i})\), \(dFit_{i}=C_{i}\)\(-\)\(TW_{i}\), we can select the best knapsack \(K_{i}\) directly for the best order. By the DP-packing, there may be many equal \(min(dFit_{i})\)s in \(K_{i^{\prime}}\)-\(K_{i^{\prime}}\) but only one \(K_{i}\) is selected (at a time), and this decision may cause the local optimal problem. To handle this problem, the top three effective policies are introduced in Algorithm 10, and the best of three best results is our final solution. However, to achieve the better results of these critical/special datasets, we add the other effective policies 4-8 in Algorithm 10 (step 2) to cover the other critical decisions; see an example in Figure 20b, i.e., select \(K_{i}\) with \(min(dFit_{i})\) at the first, last, second, before last, and mid policies (in policies 4-8). Figure 20b shows the detail of selecting the best \(K_{i}\) (\(m=10\) knapsacks, \(C_{i}\) = (10, 20, 15, 18, 12, 25, 5, 19, 9, 24)) with eight critical decisions (i.e., assume there are six \(min(dFit_{i})\)s = 0 in \(K_{i}\), \(i=1\), 3, 6, 7, 9, 10) for selecting the best \(K_{i}\) (in the best order) with one policy for one result (so\(lTP\)). In this experiment, the improved results (max (\(solTP_{i=1-8}\))) in Column 4 (Table 13) were stable under these eight policies. In each critical dataset, the results (Column 4) were improved due to the exact DPT-List packing plus the proper critical handling (by our eight policies for the best knapsack order). In the regular comparison of our mDPT-List + robust unbiased filtering (the best knapsack order) on 20 critical datasets (in Table 13), our robust unbiased filtering (using top three policies) yielded (9 of 20) best results (Column 6), which outperformed the results

Figure 20: (a) Overpacking (in the extra space of one knapsack with large total-capacity \(C^{5}\)) in critical datasets and (b) an example of eight effective policies (to handle the critical decisions). (Column 7) of using LSs of top nine orders (9 \(m\)).