Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

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/
```
Associated Topics:
College Algorithms
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search