CELKO (8/20/2014)

---

Google “bin packing” and “knapsack” problems. Ther is also a classic book availalbre as a PDF download. http://www.or.deis.unibo.it/knapsack.html. It has heavy math and awful FORTRAN.

The bottom line is that you are screwed for the general case. This is an NP Complete problem.

Also your specs need to be more precise as to how you determine the sizes; would 3 identical sized bags and 1 outlier be better than 4 near-matches? Etc.

Since you have a limited problem of 4 knapsacks and 10 items. My best guess is first partition the 10 items into 2 subset of approximately equal weight. Whatever that means and assuming it is possible. Then partition each of those recursively and hand them out to the 4 drivers.

This will require a table of 2^10 rows (1024) with all possible combinations of the weights and 0 in each column.

CREATE TABLE Routes

(partition_nbr INTEGER NOT NULL PRIMARY KEY,

r01 INTEGER NOT NULL

CHECK(r01 IN 0, 700),

r02 INTEGER NOT NULL

CHECK(r02 IN 0, 210)

…

r10 INTEGER NOT NULL

CHECK(r10 IN 0, 525));

Load the routes (exercise for the student) then

SELECT partition_nbr, (r01+r02+ ..+r10) AS wgt

FROM Routes;

Pick partitions closest to the mid point.