## 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 the superior improvement of our eight effective policies (in the extra experiment), the extra mDPT-List yielded (16 of 20) best results (Column 4), while the other 4 of 20 best results (Column 3) were fulfilled by robust filtering due to the (unbiased) preselecting and the less problem of nonunique Xs in the X-tracking by DPT-List (on small \(n^{\prime}<300\)) in each knapsack. Obviously, for the unique X, our mDPT-List (with/without filtering) yields the same result. In addition, the response times of three mDP algorithms (basic mDP, mDPT-List, and mDPT-List + filtering) were compared in this experiment (under the same 99% optimal precision). In theory, three different time complexities of these mDP algorithms are 1. O(\(mt\)\(nC\)) in the basic mDP (\(mt\) orders), 2. O(\(m^{2}\)[\(n^{2}\), \(nC\)]) in the mDPT-List (the best order), and 3. O(\(m^{2}\)\(n\)) in the fast mDPT-List + filtering (the best order). Due to our efficient unbiased filtering, the response time of our fast mDPT-List + filtering for \(n\) = 20,000 and \(m\) = 20 was less than one second, that of the best mDPT-List for \(n\) = 20,000 was 10 min, that of the basic mDP for \(n\) = 20,000 was more than one hour and so on for other large \(n\). Next to simplify the comparison and discussion (for the 0/1-mKP solving with the critical datasets), we employ the triple-right rule (right man, right place, and right time). Figure 21 displays the improvement of our multi-DPT-List\({}_{\text{TSR}}\) algorithm (our novel research track in Figure 8) to reach 99% optimal solutions in efficient time. In theory, the exact BnB algorithm can find the exact solution of the 0/1-mKP but in O(\((m+1)^{n}\)) with the right man and right place but not the right time. In practice, the multi-GH\({}^{+}\) (with 9 \(m\) LS-orders) can find the good solutions in polynomial time but those solutions may not be optimal because it only confirms the right time rule. In this study (Figure 21), we study and apply the exact DPT (in theory) and the efficient unbiased filtering (in practice) to achieve triple-right packing (right man (object), right place (knapsack), and right time (O(\(m^{2}\)\(n\)))). Our contribution is the \(mt\)-to-\(m^{2}\) reduction; see the highlight space of our improvement in Figure 21. This tight-bound reduction starts with the exact DPT for one knapsack (selecting the right object), uses the exact-fit (best) order for \(m\) knapsacks (putting the right object in the right knapsack), and ends with robust unbiased filtering (putting the right object in the right knapsack at the right time). The comparison of our multi-DPT-List + robust filtering and the recent HyMKP [34] is demonstrated in Table 14. In practice (with large \(n\) (\(\leq\)10,000 in this experiment)), our multi-DPT-List + robust filtering yielded 99% optimal results in O(\(m^{2}\)\(n\)); see results in Tables 5-12,

Figure 21: The improvement of our multi-DPT\({}_{\text{TSR}}\) algorithm for solving the 0/1-mKP (\(m\) knapsacks) when dealing with the critical datasets. while the results of quick multi-GH\({}^{+}\) in O(\(m^{2}n\)) were not optimal. For the HyMKP study [34], there is no available result for \(n>500\) since for large \(n\) the partial BnB (MULKNAP program) in the HyMKP (Algorithm 5) may not find the optimal solution in \(\tau\) secs. Then, the reflect multi-graph MKP (with increasing \(n\)-weights (\(w_{j}\)) in Algorithm 6 (O(\(mnC\))) can provide the comparable results to our multi-DPT-List (with top nine orders) in the regular datasets, according to the looping on weights and C, similar to the DP (Algorithm 1) for each of \(m\) knapsacks. For the irregular datasets, v-rounds of decompositions of HyMKP are used to improve the initial solution. However, (for large \(n\)) the process of Algorithm 6 may take a long time to reach the 99% optimal solutions due to its complexity O(\(mnC\)), while our exact-fit best (knapsack) order of multi-DPT-List + efficient filtering in O(\(m^{2}n\)) can find 99% optimal solutions as \(m!\) orders.