Shuji YAMAMURA, Akio OKUMURA, Takeshi SHIMOMURA, and Atsushi NUNOME
May 29, 1997
Solve m 0/1 knapsack problems and compete on the value of the package packed in the knapsack given by each problem i (0 ≦ i ≦ m) and the total execution time.
Solve all m problems within the time limit. You'll be ranked in order of the sum of m value points and one time point.
We choose one between the following two algorithms in compliance with the scale of a problem. 

This figure shows the DDD creation process when you get an optimul solution with given three objects in that table. (Provided that the weight limit w is 4.)
In initial condition, the DDD is composed of two nodes, a root node and a leaf node. A leaf node has two numerical information, the sum of weights and the sum of values. The upper side of a leaf node is the sum of weights, and the lower side is the sum of values in that 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 node by inserting an object between leaf node and other object node successively.
If the sum of weights have been over the weight limit of the knapsack by appending the object x_{1} or x_{2}, set the link NULL and do not generate new leaf node.
Thus, the following figure shows the final DDD that have been appended all objects.
Finally, find the mostvalued node in all leaf nodes and trace back links from the node to the root node. Then, you should get optimul solution.
By using this algorithm, the number of leaf nodes is the knapsack's limited weight + 1 at most. So, the leaf nodes will not increase explosively as you construct a traditional BTree. When you append an object to the DDD, you have only to process the leaf nodes which have been generated at that moment. In that respect, DDD algorithm is superior to DPA.
A large number of objects will make too many leaf nodes during DDD construction. So, our algorithm avoids this problem by Most Valuable Selection(MVS).
MVS reduces the leaf node by grouping some leaf nodes. 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 
In case of solving the problem number 6 to 8 with DPA,
Problem Number  6  7  8 
Time(sec)  0.91  3.59  3.56 
yamamu2salia.dj.kit.ac.jp
okumur2aalia.dj.kit.ac.jp
shimom2talia.dj.kit.ac.jp
nunome2aalia.dj.kit.ac.jp