Find a variables in array, which sum is closest to target sum

Question

I have an array of variables {500, 450, 455, 700, 800,...}, and I need to find lets say 10 variables from array which generates closest sum to 4500. Is there any algorithm or method in C# or C++?

Answer 1

This is exactly the problem of 0/1 knapsack which can be solved in O(n^2) using dynamic programming (where n is the sum we want to reach, eg 4500) described here http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem. The dp array created contains information for what you want.

Answer 2

I would start off with a brute-force method. Your requirements do not seem popular enough for a library or algorithm to be posted.

After I implemented the brute force method and got it working, I would profile it within the working system. If the algorithm need to be faster or take up less space, I would then optimize it accordingly.

Here's my suggested algorithm:

for index = 0; index < NUMBER_QUANTITY - 10; ++ index
{
  Create a vector with 10 numbers from the array.
  Create a sum of the 10 numbers.
  Store the vector and sum into a std::map<int, vector<int> >.
}

Iterate through the map until a key is found that is greater than 4500.
Your closest values will be at (iterator + 0) and (iterator - 1).
Using the iterator, fetch the vector out of the map and list the numbers in the map.

Edit 1: Optimized
Instead of storing each vector of 10 numbers into a map, you could keep a single vector that is updated if it's sum is closer to the target value.

int sum_delta = 4500;
int sum = 0;
for (...)  
{
  Calculate temporary sum of the 10 numbers.
  Calculate temporary sum delta:  abs(4500 - sum);
  if (temporary sum delta < sum_delta)
  {
     sum = temporary sum;
     sum_delta = temporary sum delta;
     copy 10 numbers into vector
  }
}

Answer 3

The C++ STL library provides a function for iterating over permutations, but not combinations. However, there is a way around that.

To give you an idea:

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cstdlib>

int main()
{
        const int numbers[] = { 500, 450, 455, 700, 800, 123, 234, 345, 456, 567, 678, 789, 890, 901, 854, 365, 785, 987, 876, 765, 654, 543, 432, 321};

        const std::size_t n = sizeof(numbers) / sizeof(*numbers);
        const std::size_t r = 10;
        const int targetSum = 4500;

        std::vector<int> numvec(&numbers[0], &numbers[n]);

        std::vector<bool> indices(n);
        std::fill(indices.begin() + n - r, indices.end(), true);

        int bestDelta = targetSum;
        std::vector<int> bestCombination;

        do {
                std::vector<int> combination;

                for (std::size_t i = 0; i < n; ++i) {
                        if (indices[i]) {
                                combination.push_back(numvec.at(i));
                        }
                }

                int sum = std::accumulate(combination.begin(), combination.end(), 0);
                int delta = abs(sum - targetSum);
                if (delta < bestDelta) {
                        bestDelta = delta;
                        bestCombination = combination;

                        for (std::vector<int>::const_iterator it = combination.begin(), end = combination.end(); it != end; ++it) {
                                if (it != combination.begin()) {
                                        std::cout << "+";
                                }
                                std::cout << *it;
                        }
                        std::cout << "=" << sum << std::endl;
                }

                if (sum == targetSum) {
                        break;
                }
        } while (std::next_permutation(indices.begin(), indices.end()));
        return 0;
}

Could certainly be optimized... Credit to this post for the combinations algorithm.