## 2 Related Work
### 0/1-KP Solving by Dynamic Programming Algorithm  
For 0/1-KP solving, let \(tp[C]\) be an array of total profits, \(soltp\) be a maximum total-profit, \(soltp\) be a total-weight (\(\leq\)\(C\)), and \(solx[n]\) be an array of solution X (\(x_{j}\) = 0/1). Algorithm 1 presents the basic DP [11] with two functions (preprocessing and X-tracking on a 2D array or a matrix (\(n\times C\))) to find the optimal solution (\(soltp\), \(soltv\), \(solx[n]\)) in O(\(nC\)). For example, consider \(n\) = 6, \(C\) = 18, \(P\) = {42, 39, 38, 37, 35, 38}, and \(W\) = {10, 11, 11, 8, 10, 9}, Figure 2 displays the result of preprocessing (\(soltp\) = 79) and X-tracking (\(solx\) = {1, 4} from \(soltp\) = 79) by applying Algorithm 1. However, using the 2D array (\(n\times C\)) reserves a huge space, which is not practical if \(C>n^{2}\). Thus, the fast DP (Algorithm 2) [11] uses a 1D array (of \(C\) elements) to find \(soltp\) in O(\(nC\)) but without \(solx[n]\) since the 1D array of the last \(tp\)-result cannot support the X-tracking (for all selected objects). Finally, the complete DP (Algorithm 3) [11] (p. 24) uses a 1D array for the full optimal solution (\(soltp\), \(soltv\), \(solx[n]\)) by repeating the fast DP (for \(k\) selected objects) in O(\(knC\)).  
Figure 2: An example of 0/1-KP solving (\(n\) = 6, \(C\) = 18) of the basic DP (Algorithm 1): \(tp\)-results and \(soltp\) = 79 (optimal) in an \(n\)\(NC\)-matrix and X-tracking for \(solx\) = {1, 4}.  
```
1. for (\(d=0\) to C) \(tp[0,d]=0\);
2. for (\(j=1\) to \(n\)) do // preprocessing for \(soltp\)
3. for (\(d=0\) to \(w_{j-1}\)) \(tp[j,d]=tp[j-1,d]\);
4. for (\(d=w_{j}\) to C) do
5. if (\(tp[j-1,d\)-\(w_{j}]+p_{j}>tp[j-1,d]\)) then \(tp[j,d]=tp[j-1,d\)-\(w_{j}]+p_{j}\);
6. else \(tp[j,d]=tp[j-1,d]\);
7. end for \(d\);
8. end for \(j\);
9. \(soltp=tp[n,C]\);
10. \(d=C;j=n;solx=\emptyset\); // X-tracking for \(solx\)
11. do// X-tracking for \(solx\)
12. while (\(tp[j,d]=tp[j-1,d]\)) \(j=j-1\); // move up
13. \(solx=solx\) U \(\{j\}\); \(pp=tp[j,d]\).\(p_{j};j=j-1\);
14. while (\(tp[j,d-1]\geq pp\) and \(pp>0\)) \(d=d-1\); // move left
15. while (\(pp>0\) and \(j\geq 1\)).
```  
**Algorithm 1**Basic DP with 2D array (for \(soltp\), \(soltw\), \(solx[n]\)) in O(\(nC\)).  
```
1. for (\(d=0\) to C) \(tp[d]=0\);
2. for (\(j=1\) to \(n\)) do // preprocessing for \(soltp\)
3. for (\(d=0\) to \(C\)) do // preprocessing for \(soltp\)
4. for (\(j=1\) to \(n\)) do // preprocessing for \(soltp\)
5. for (\(d=C\)' down to \(w_{j}\)) do
6. if (\(tp[d\)-\(w_{j}]+p_{j}>tp[d]\)) then
7. \(x[d]=j;tp[d]=tp[d\)-\(w_{j}]+p_{j}\);
8. end for \(d\);
9. end for \(j\);
10. \(r=x[C\)']; // find \(solx\) (a selected object)
11. \(solx=solx\) U \(\{r\}\); \(k=k+1\);
12. \(n^{\prime}=r-1\); \(C^{\prime}=C\)' \(w_{j}\);
13. while (\(C\)'\(>0\)); // repeat for \(k\) selected objects
14. \(soltp=tp[C]\).
```  
**Algorithm 2**Fast DP with 1D array (for \(soltp\), \(soltw\)) in O(\(nC\)).  
```
1. for (\(d=0\) to C) \(tp[d]=0\);
2. for (\(j=1\) to \(n\)) do // preprocessing for \(soltp\)
3. for (\(d=C\) down to \(w_{j}\)) do
4. if (\(tp[d-w_{j}]+p_{j}>tp[d]\)) then \(tp[d]=tp[d\)-\(w_{j}]+p_{j}\);
5. end for \(d\);
6. end for \(j\);
7. end for \(j\);
8. end for
```  
**Algorithm 3**Full DP with 1D array (for \(soltp\), \(soltw\)) in O(\(knC\)).