The Details of DDD Algorithm for Parallel Software Contest (PSC'97)


May 29, 1997

Given Problems

Solve m 0/1 knapsack problems and compete on the value of the package packed in the knapsack given by each problem i (0 ≦ im) and the total execution time.

Scoring Rule

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.

At the quality of result
Score 10 points to 1 point in order of the value of result.
At calculation time
The program which have been got more than 1 point in some problems can score 10 points to 1 point in order of quickness.

The Condition of Problem

Our Solution

We choose one between the following two algorithms in compliance with the scale of a problem.
  1. DPA(Dynamic Programming Algorithm)
  2. DDD(Dynamic Decision Diagram) Algorithm

DDD Algorithm

  • Dynamically construction method of a B-Tree inserting each object
  • You can get an optimul solution by tracing back the B-Tree from the leaf node.

[How to make the DDD]

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 x1. At this time, insert node x1 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 x1", and the right one is "the leaf node if you append the object x1".

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 x1 or x2, 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.

[How to make the DDD part2]

Finally, find the most-valued 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 B-Tree. 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.

Most Valuable Selection(MVS)

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.

Most Valuable Selection

The Relationship of Grouping Parameter and Calculation Time

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
Machine: Sun Ultra1(167MHz), 128MB Memory

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

Known Problems


Back to ARK