Suppose we are given a set of n positive integers. Our task is to arrange these integers into two piles, or "bins", so that the sum of the integers in one pile is equal to the sum of the integers in the other pile.

For example, given the integers

(19, 23, 32, 42, 50, 62, 77, 88, 89, 105, 114, 123, 176)

These numbers sum to 1000. Can they be divided into two bins, bin A and bin B, such that the sum of the integers in each bin is 500?

There is an obvious nondeterministic algorithm: for each number, put it in the correct bin. This requires linear time.

There is also a fairly easy deterministic algorithm. There are 13 numbers (n=13), so form the 13-bit binary number 0000000000000. For i ranging from 1 to 13: if bit i is zero, put integer i into bin A; if bit i is one, put integer i into bin B. Test the resultant arrangement. If you don't have a solution yet, add 1 to the binary number and try again. If you reach 1111111111111, stop and conclude that there is no solution.

This is a fairly simple algorithm; the only problem is that it takes O(2^{n})
time, that is, *exponential time.* In the above example, we may need to try as many
as 2^{13} arrangements. This is fine for small values of n (such as 13), but
becomes unreasonable for large values of n.

You can find many shortcuts for problems such as this, but the best you can do is
improve the coefficients. The time complexity remains O(2^{n}). Problems that
require exponential time are referred to as *intractable* problems.

By the way, there are many variations on this problem.

- You can have multiple bins.
- You can have a single bin, and the object is to pack as much as possible into it.
- You can pack objects with multiple dimensions (volume and weight, for example).
- Objects have not only a size but also a value, and the object is to pack as much value as possible.

...and so on.

Copyright © 1996 by David Matuszek

Last modified Apr 23, 1996