## 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.1 Top Nine Knapsack Orders for Regular Datasets  
Initially, the top nine (knapsack) orders are introduced in our multi-DPT-List\({}_{\text{TSR}}\) algorithm, which are good enough to solve the 0/1-mKP with 99% optimal solutions for the regular datasets. Each of the top nine orders is obtained by sorting \(m\) capacities (\(C_{i}\), \(i\) = 1, 2, 3,..., \(m\)). For example (\(m\) = 5), the forward order (F) of capacities C = (66, 26, 80, 96, 70) is (1, 2, 3, 4, 5), and the top three orders are increasing (inc) = (2, 1, 5, 3, 4), decreasing (dec) = (4, 3, 5, 1, 2), and combined inc-dec = (2, 4, 1, 3, 5). In this study, the top nine effective orders include increasing (inc), decreasing (dec), combining inc-dec, combining dec-inc, forward (F), backward (B), odd-even (of F), odd-even (of inc), and odd-even (of dec); see a corresponding example in Figure 9. Moreover, each result of the top nine orders can be improved by the Latin square (LS) of \(m\) permutations to achieve at least 99% optimal solutions (for the regular datasets). In practice, the partial LS (first nine permutations) of the top nine orders are used to preserve the complexity in O(\(m[n^{2}\), \(nC]\)) for \(m>9\).  
Algorithm 9 (multi-DPT-List\({}_{\text{TSR}}\)) is proposed to solve the 0/1-mKP for each order (of top nine orders/Latin squares of nine orders) in O(\(m[n^{2}\), \(nC]\)). Moreover, in some cases,  
Figure 8: (a) Our novel research track for solving 0/1-mKP in polynomial time with 99% optimal solutions and (b) our multi-DPT-List\({}_{\text{TSR}}\) algorithm and efficient parallel models.  
Figure 9: An example of the top nine (knapsack) orders and their Latin squares (of \(m\) permutations) for \(m=5\) knapsacks and \(C=\) (66, 26, 80, 96, 70).  
there are different Xs (in X-tracking from many _soltws_ of max _soltw_), called the nonunique solution Xs, in each knapsack. For the 0/1-KP, X-tracking can start at (_soltp_, min _soltw_) or (_soltp_, max _soltw_) for different Xs. For the 0/1-mKP (Algorithm 9: Lines 5-6), knapsack \(i\) (\(\leq m-1\)) should start at (_soltp_, max _soltw_) to allow the better result for the remaining knapsacks, while the last one (\(i=m\)) can start at (_soltp_, min _soltw_). For example, given a dataset (\(n=25\), \(m=4\), \(C=\) (20, 30, 40, 50), \(P=\) {17, 10, 14, 18, 14, 15, 27, 11, 12, 16, 24, 13, 22, 26, 15, 16, 18, 22, 19, 24, 21, 13, 14, 11, 28], and \(W=\) {11, 4, 14, 3, 7, 5, 4, 4, 10, 12, 6, 5, 7, 6, 8, 5, 11, 9, 5, 10, 8, 5, 3, 6, 8]). In knapsacks \(K_{1}-K_{2}\), there are unique X-tracking results, but nonunique X-results occur in knapsack \(K_{3}\) (\(C_{3}=40\), \(n^{*}=15\), \(j=\) {0, 2, 4, 5, 8, 9, 11, 14, 15, 16, 17, 19, 20, 21, 23)). Figure 9(a) shows the result (393) when starting X-tracking at (103, 39), min _soltw_ = 39 in \(K_{3}\). Figure 9(b) shows the optimal result (398) when starting X-tracking at (103, 40), max _soltw_ = 40 in \(K_{3}\), leading to the better result in knapsack \(K_{4}\) (select \(j=0\) (\(w_{0}=11\), \(p_{0}=17\)) instead of \(j=8\) (\(w_{8}=10\), \(p_{8}=12\)) in Figure 9(a)). Note: In parallel (\(p=m\)), we can assign one order per processor for at most \(m\) permutation orders (for independent computing for \(p\) solutions (at the same time) before selecting the best result).  
Figure 10: An example (\(n=25\), \(m=4\), \(C=\) (20, 30, 40, 50)) of two X-tracking with nonunique solution Xs in \(K_{3}\): (**a**) start tracking from (_soltp_, min _soltw_) and (**b**) start tracking from (_soltp_, max _soltw_).