Shuji YAMAMURA, Akio OKUMURA, Takeshi SHIMOMURA, and Atsushi NUNOME
May 29, 1997
Solve m 0/1 knapsack problems, competing based on the value of the items packed in the knapsack for each problem i (0 ≦ i ≦ m) and the total execution time.
Solve all m problems within the time limit. Ranking is based on the total of the m value points plus one time point.
We choose between the following two algorithms based on the scale of the problem. 

This figure illustrates the DDD creation process for obtaining an optimul solution with three given objects from the table. (Assuming the weight limit w is 4.)
Initially, the DDD consists of two nodes: a root node and a leaf node. A leaf node contains two numerical values: the sum of weights (upper side) and the sum of values (lower side) in the figure.
First, construct the DDD by appending the object x_{1}. At this time, insert node x_{1} between the root node and the leaf node. Then, the figure shows two newly generated nodes. The left one is "the leaf node if you do not append the object x_{1}", and the right one is "the leaf node if you append the object x_{1}".
Similarly, construct new nodes by successively inserting an object between a leaf node and another object node.
If the sum of weights exceeds the weight limit of the knapsack when appending object x_{1} or x_{2}, set the link NULL and do not generate a new leaf node.
Thus, the following figure shows the final DDD that have been appended all objects.
Finally, find the highestvalued node among all leaf nodes and trace the links back from this node to the root node to obtain the optimul solution.
Using this algorithm, the number of leaf nodes is at most the knapsack's weight limit plus 1. Thus, leaf nodes do not increase explosively as in a traditional Binary Tree. When appending an object to the DDD, only the leaf nodes generated at that moment need processing. In this respect, the DDD algorithm is superior to the DPA.
A large number of objects can create too many leaf nodes during DDD construction. Our algorithm avoids this problem using Most Valuable Selection (MVS).
MVS reduces the number of leaf nodes by grouping them. The following figure shows the condition of the leaf nodes.
Problem Number  1  2  3  4  5  6  7  8  9 
The Number of Objects  200  200  200  300  300  42  100  100  500 
The Size of Knapsacks  227800  121700  52400  334200  181050  14320  28084  28205  700544 
The Number of Groups(Final)  38386  38386  38386  25281  25281  191555  78386  78386  14938 
The Number of Groups(Optimul)  832  1255  4764  9033  6706  754  28085  3526  4766 
Optimul Time(sec)  0.53  0.79  3.26  8.99  6.60  0.09  7.40  0.91  6.68 
For solving the problems 6 to 8 using DPA,
Problem Number  6  7  8 
Time(sec)  0.91  3.59  3.56 
Shuji Yamamura (yamamu2salia.dj.kit.ac.jp)
Akio Okumura (okumur2aalia.dj.kit.ac.jp)
Takeshi Shimomura (shimom2talia.dj.kit.ac.jp)
Atsushi Nunome (nunome2aalia.dj.kit.ac.jp)
All email addresses listed here are correct at the time of publication and are no longer valid.