[Overview] [Previous] [Next]
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(2n) time, that is, exponential time. In the above example, we may need to try as many as 213 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(2n). Problems that require exponential time are referred to as intractable problems.
By the way, there are many variations on this problem.
...and so on.
Copyright © 1996 by David Matuszek
Last modified Apr 23, 1996