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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.