Matching Invoices with Report Totals

Date: 10/31/2000 at 07:35:01
From: Sarah Procter
Subject: Adding given numbers to get a given total

This is a real-life problem, having to do with trying to ascertain 
which invoices belong to which report.

I have 14 numbers that represent the invoices:

     397.16   397.16   569.65   954.5    1310.89  1383.87  1463.49   
     1528.91  1619.9   1644.54  1727.97  1776.29  1963.05  2022.74

and two that represent the report totals:

     9144.07  3777.23

When you add the right combination of invoices together you should get 
the report totals. Finding this combination proves very difficult. 
Numbers cannot be used twice.

I approached this problem using an Excel spreadsheet. I sorted the 
invoices in ascending order and then tried combinations that gave 
totals similar to the report totals, and then adjusted the combination 
to increase/decrease the total accordingly.

For example,

     569.65 + 1463.49 + 1727.97 = 3761.11  

Too small. Change to 

     397.16 + 397.16 + 569.65 + 954.5 + 1463.46 = 3781.96 

Too big. And so on.

That's as close as I got on the 3777.23 figure but eventually found 
that

     9144.06 = 1310.89 + 569.65 + 954.5 + 1963.05 + 2022.74 + 397.16 + 
               397.16 + 1528.91

But it is not possible to derive the 3777.23 from the remaining 
invoices.

We have this problem at work fairly frequently and it is frustrating 
and time-consuming. Is there a faster, more structured way of doing 
this, and can you tell me if there's a way of telling whether it is 
even possible to get the given total from a group of numbers?

Many thanks for any assistance on this.

Date: 10/31/2000 at 10:25:39
From: Doctor Rob
Subject: Re: Adding given numbers to get a given total

Thanks for writing to Ask Dr. Math, Sarah.

This is a classic problem called the Zero-One Knapsack Problem. If you 
have a set of n given numbers, there are 2^n possible subsets of them 
which could be the right one. The only method that is guaranteed to 
work to find the right subset is to try them systematically. In the 
case of n = 14, above, the number to try is 2^14 = 16,384. Of course 
you can eliminate subsets which give totals which are obviously too 
large or too small. Even so, there are a very large number of trials 
that would have to be made. Unfortunately, this is also the only way 
to prove that no subset will make a given total.

There are some tricks that can be used to eliminate subsets that will 
not give the right answer. One is to look at the last digit of each 
number, and to see whether they add up to the last digit of the target 
total. If not, that subset can be eliminated.

Another trick is to split the numbers into two sets of 7 each, and 
write down the sums of all 2^7 = 128 subsets of each of the smaller 
sets in two lists of length 128. Then if the target total is not on 
either list, you need to find two numbers, one from each list, whose 
sum is the target total. This is not as bad as searching through all 
16,384 possibilities.

One systematic way to enumerate the subsets is to use lexicographic 
(or dictionary) order. Each subset corresponds to an n-long string of 
1's and 0's. The first digit is a 1 if the largest number is in the 
subset, and 0 if not. The second digit is a 1 if the next-to-largest 
number is in the subset, and 0 if not, and so on. For example, 
1000...000111 would represent the largest number and the 3 smallest 
numbers of the list.  These strings can be listed in increasing 
(lexicographic) order:

    00000...000000
    00000...000001
    00000...000010
    00000...000011
    00000...000100
    00000...000101
    00000...000110
    00000...000111
    00000...001000
          :
    11111...111100
    11111...111101
    11111...111110
    11111...111111

There are 2^n of these strings and 2^n subsets of the n given numbers. 
This order will tend to give you small sums first and large ones 
later. Reverse the order if you want large sums first.

I redid your computations, and found that your answers were the 
closest that could be done. By the way, a computer can sort through 
all the possibilities very rapidly indeed.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/