How do I determine if any combination of the sum o

Question

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 

Answer 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;
    }
}

Answer 2

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

• Algorithm to find which numbers from a list of size n sum to another number

---

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

Answer 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.)

Answer 4

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.

Answer 5

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:

• Subset sum Problem
• Subset Sum algorithm
• Optimizing subset sum implementation