## 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  
For the irregular datasets, we may use all possible \(m!\) orders to find at least 99% optimal solutions in O(\(m!\)\([n,\,nC]\)) but \(m!\) orders work on small \(m\) only. Thus, for large \(m\), to achieve the optimal precision as \(m!\) orders, we propose the exact-fit (best) knapsack order (Algorithm 10) in O(\(m^{2}[n^{2},\,nC]\)), where both internal and external effects must be solved by the exact DPT-List\({}_{\text{TSR}}\) algorithm. For the external effect (among \(m\) knapsacks), the DPT-List\({}_{\text{TSR}}\) algorithm is used for computing the exact (\(TP_{i},\,TW_{i}\)) in each of available knapsacks before selecting \(K_{i}\) with the best exact-fit\({}_{i}=min(dFit_{i})\), where different \(Fit_{i}\) (\(dFit_{i}\)) = \(C_{i}-TW_{i}\), \(\forall i\leq m\). For instance, Figure 11 shows the exact-fit (best) order for \(m=5\), \(C\) = (66, 26, 80, 96, 70), \(n=33\), \(P\) = [18, 44, 7, 21, 22, 29, 42, 24, 36, 17, 13, 23, 12, 25, 15, 41, 15, 19, 33, 5, 8, 18, 28, 25, 12, 30, 19, 14, 48, 25, 16, 23, 25], and \(W\) = [6, 12, 16, 12, 14, 14, 5, 12, 15, 10, 17, 14, 9, 19, 5, 7, 12, 8, 14, 15, 14, 12, 7, 6, 13, 15, 10, 14, 8, 12, 10]. In Figure 11b, the best order (2, 4, 1, 5, 3) is computed in \(m(m+1)/2\) = 15 steps by our exact DPT-List\({}_{\text{TSR}}\) algorithm to achieve the optimal result (726). * In the first \(K_{i}\) selection, there are \(m\,dFit_{i}\)-results (in \(m\) = 5 steps) with two \(min(dFit_{i})\) = 0 (in \(K_{2}\), \(K_{3}\)) and \(K_{2}\) (\(min\)\(C_{2}\)) is selected (see conditions in Step 2 of Algorithm 10). * In the second \(K_{i}\) selection, there are 4 \(dFit_{i}\)-results and \(K_{4}\) (\(min(dFit_{4})\) = 0) is selected. * In the third \(K_{i}\) selection, there are 3 \(dFit_{i}\)-results and \(K_{1}\) (\(min(dFit_{1})\) = 0) is selected. * In the fourth \(K_{i}\) selection, there are 2 \(dFit_{i}\)-results and \(K_{5}\) (\(min(dFit_{5})\) = 0) is selected. * In the fifth \(K_{i}\) selection, the last \(K_{3}\) (\(min(dFit_{3})\) = 0) in the last step is selected. Moreover, for critical decisions in some datasets, there are equal \(min(dFit_{i})\)s in \(K_{f}-K_{f^{\prime}}\). Then, three extra policies (Step 2 in Algorithm 10) are introduced to find the best of the three best results (for the good results as \(m!\) orders as much as possible). ```
Step 1: apply DPT-List\({}_{\text{TSR}}\) for \((TP_{i},TW_{i})\) on each of \(m\) knapsacks in O(\(m[n^{2},\,nC]\)) and O(\([n^{2},\,nC]\)) in parallel (\(p=m\)). Step 2: select best \(K_{i}\) with \(min(dFit_{i})\); \(dFit_{i}=C_{i}-TW_{i}\) (\(i\) = 1, 2,..., \(m\)). In Step 2, for critical \(min(dFit_{i})\), each of the three policies is applied. ```  
**Algorithm 10**multi-DPT-List\({}_{\text{TSR}}\) (the exact-fit (best) knapsack order). ``` Step 2: apply DPT-List\({}_{\text{TSR}}\) for \((TP_{i},TW_{i})\) on each of \(m\) knapsacks in O(\(m[n^{2},\,nC]\)) and O(\([n^{2},\,nC]\)) in parallel (\(p=m\)). Step 3: select best \(K_{i}\) with \(min(dFit_{i})\); \(dFit_{i}=C_{i}-TW_{i}\) (\(i\) = 1, 2,..., \(m\)). In Step 4, for critical \(min(dFit_{i})\), each of the three policies is applied. In parallel, the multi-DPT-List\({}_{\text{TSR}}\) (the exact-fit (best) order) can be processed in O(\(m[n^{2},nC]\)) by \(p=m\). However, O(\(mnC\)) in the worst case is not efficient for large \(m\), \(n\), and \(C\). Thus, in Section 4.2, robust unbiased filtering (our key contribution) is presented in efficient O(\(m^{2}n\)) by \(p=1\) and O(\(mn\)) by \(p=m\) while retaining 99% exact precision. ### Efficient Robust Unbiased Filtering for Polynomial Time Reduction

In our novel research track (Figure 8a), the contribution in polynomial time is achieved by robust unbiased filtering in O(\(m^{2}(n+C^{\prime})\)) or O(\(m^{2}n\)) on \(C^{\prime}\) (\(<<C\)) \(<\) large \(n\) while retaining 99% optimal solutions.