0

I have a set of values below. What I need to find out is if any combination of these value's sums a certain value (46,134.77 in this case). What is the best way to figure this out? Of course it would take hours to do it manually.

And I would need to know what the combination is if it returned true. I could set this up in Excel VBA, or a C# app. Whatever would work. I just have no clue how to get there.

 125.00 
 1,000.00 
 1,039.36 
 1,171.60 
 1,200.00 
 1,320.00 
 1,680.00 
 1,757.20 
 1,768.80 
 1,970.00 
 2,231.25 
 2,300.00 
 2,369.25 
 2,589.20 
 2,720.00 
 2,887.50 
 3,000.00 
 3,085.00 
 3,142.60 
 3,174.40 
 3,742.70 
 3,847.20 
 5,609.25 
 5,881.05 
 12,240.48 
 14,112.00 
 29,318.07 
 32,551.80
Community
  • 1
  • 1
Barrett Kuethen
  • 1,864
  • 7
  • 25
  • 33
  • Possible duplicate of http://stackoverflow.com/questions/403865/algorithm-to-sum-up-a-list-of-numbers-for-all-combinations – srgerg Jan 31 '12 at 00:00
  • Sounds like a binary search tree where the value of each node is the sum of nodes above when true. – EtherDragon Jan 31 '12 at 00:00
  • possible duplicate of [Algorithm to find which numbers from a list of size n sum to another number](http://stackoverflow.com/questions/83547/algorithm-to-find-which-numbers-from-a-list-of-size-n-sum-to-another-number) – Austin Salonen Jan 31 '12 at 00:13
  • 9
    You and everyone else would like a solution to this problem. This waiter, for example: http://xkcd.com/287/ – Eric Lippert Jan 31 '12 at 00:17

5 Answers5

6

As already mentioned in paislee's answer, this is a variation on the knapsack problem. In fact, this specific problem is called the subset sum problem, and like the knapsack problem, it is NP-complete.

The linked Wikipedia page shows how to solve the problem using dynamic programming, but note that due to its NP completeness it will always be slow/impossible to solve if you make your list of integers too large.

Here are some more related SO questions:

Community
  • 1
  • 1
AVH
  • 11,349
  • 4
  • 34
  • 43
3

This is almost precisely a bounded knapsack problem, one of the most well-studied computation problems in history. Locally:

NP Complete means you should get ready to write a giant loop summing up every (or nearly every) combination of numbers.

I'd recommend not doing this by hand. Several hours is a gross underestimation. It would take your whole life. For example there are over 40 million combinations of 14 numbers when choosing from a pool of 28. (That's just the 14's).

Community
  • 1
  • 1
calebds
  • 25,670
  • 9
  • 46
  • 74
  • Almost, at least -- the knapsack problem is, strictly speaking, to find the **closest** combination which doesn't exceed the target. –  Jan 31 '12 at 00:05
3

What you are describing is a variant of the Knapsack problem. It's computationally Hard to solve effectively, but for a set this small it's feasible.

The exact combination of numbers for this specific input is:

29,318.07 + 5,881.05 + 3,174.40 + 3,085.00 + 2,231.25 + 1,320.00 + 1,000.00 + 125.00

I used the following Perl script to determine this solution:

sub knapsack {
    my ($target, $path, @vals) = @_;
    if ($target == 0) {
        print "Got it: @$path\n";
        exit;
    }
    while (my $val = pop @vals) {
        next if $val > $target;
        knapsack($target - $val, [@$path, $val], @vals);
    }
}

knapsack(46134_77, [], (
    125_00,  1000_00, 1039_36, 1171_60, 1200_00, 1320_00, 1680_00, 1757_20,
    1768_80, 1970_00, 2231_25, 2300_00, 2369_25, 2589_20, 2720_00, 2887_50,
    3000_00, 3085_00, 3142_60, 3174_40, 3742_70, 3847_20, 5609_25, 5881_05,
    12240_48, 14112_00, 29318_07, 32551_80,
));

Note that I've converted your decimal values to integers (by multiplying them all by 100), as floating-point comparisons are a minefield. (See What Every Computer Scientist Should Know About Floating-Point Arithmetic for details.)

1

Read other answers/comments first. Here is a solution that could be used for a small set of data.

double[] nums = new double[] { 10,20,30,40,50,60,70,80,90,100,150,200,250,300,400,500};

Parallel.ForEach(GetIndexes(nums.Length), list =>
{
    if (list.Select(n => nums[n]).Sum()==350)
    {
        Console.WriteLine(list.Aggregate("", (s, n) => s += nums[n] + " "));
    }
});

IEnumerable<IEnumerable<int>> GetIndexes(int count)
{
    for (ulong l = 0; l < Math.Pow(2, count); l++)
    {
        List<int> list = new List<int>();
        BitArray bits = new BitArray(BitConverter.GetBytes(l));
        for (int i = 0; i < sizeof(ulong)*8; i++)
        {
            if (bits.Get(i)) list.Add(i);
        }
        yield return list;
    }
}
L.B
  • 114,136
  • 19
  • 178
  • 224
  • This solution only works if you use each of the numbers in the list only once. for example it wont find 20 in nums = {10} – cobolstinks Jun 13 '18 at 21:38
0

Yes duskwuff is right. The ONLY combination that adds up to 46134.77 is this one:

125 1,000.00 1,320.00 2,231.25 3,085.00 3,174.40 5,881.05 29,318.07

It took 2 seconds to find out. I have used SumMatch Excel add-in.

catpol
  • 68
  • 1
  • 4