Interesting problem

[dancivuk]

Okay so I have a set of integers that I enter, I have a number N which I also enter, as well as a number K that I also enter.
I have to pick K numbers from the set whose sum is the closest to N

So for example lets say that my set goes S={1,5,9,13), N is 7 and K is 2;
I would have to pick 2 numbers out of the set and their sum would have to be the closest to 7.
In this case, the result would be 1,5 as 6 is the closest sum to 7 from the set.

I imagine I would need two or three for loops that would calculate all possible sums of K numbers, and an array that stores values of all the sums, pick the one closest to N, and print the numbers from the set that add up to it.
However, I have no idea how to start as for loops aren't my best, and I'm not sure how I would print the numbers from the set once I have the closest sum.
Any help would be appreciated

[Handy Andy]

Hello dancivuk,

After thinking about the problem for awhile I came up with this:

#include <iostream>
#include <array>


int main()
{
	std::array<int, 8> S = { 1 , 4, 9, 6, 13, 7, 5, 3 };
	int N{ 7 }, K{ 2 }, start{ 1 };

	std::cout << "\n Target number is: " << N << std::endl;

	for (size_t lpo = 0; lpo < S.size(); lpo++)
	{
		for (size_t lpi = start; lpi < S.size(); lpi++)
		{
			int test = S[lpo] + S[lpi];
			if ((test == N - 1 || test == N || test == N + 1) && S[lpo] != S[lpi])
			{
				std::cout << "\n " << S[lpo] << " + " << S[lpi] << " = " << test << std::endl;
			}
		}

		start++;
	}

}

Notice the && part of the if statement. I put that there to avoid adding the same number to itself. Then I found that adding "start++;" at line 23 to avoided opposites like "3 + 5" and "5 + 3".

This works when "K = 2", but if "K = 3" or more it will have to be adjusted. Lines 12 - 24 can be put in a function and those lines could be replaced with a switch/case.

Hope that helps,

Andy

[TheIdeasMan]

I imagine I would need two or three for loops that would calculate all possible sums of K numbers, and an array that stores values of all the sums, pick the one closest to N, and print the numbers from the set that add up to it.

With this type of problem one has to limit the amount of work being done as much as possible, imagine if the the set had 1 million items and K was a relatively large number.

Instead of all possible sums of K numbers, only the ones between the previous and next values in the set relative to N. If N+1 means the next value in the set after N, maybe one could work backwards from there? Certainly don't need to sum anything larger than N+1.

Some other ideas:

Try it on an identity set : {1, 2,3 ... 100} it's trivial for 2 numbers, but not so for more than that. Multiple answers?

The larger K is, the smaller the numbers which make the sum. Would N/K be a starting point?

Just some ideas :+)

[gunnerfunner]

comments within the code:

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <tuple>
#include <limits>
#include <cmath>

constexpr auto SIZE = 2;
constexpr auto FIXED = 7;

int NchooseR(const int& n, int& r ); // number of combinations of r from n;
std::vector<std::vector<int>> allCombos (const int& n, int r ); // actual combinations of r from n;

int main()
{
    std::vector<int> S = { 1, 5, 9, 13};

    std::map<int, std::pair<int, int>> distancePoints{};

    int minDistance = std::numeric_limits<int>::max();
    for (const auto& elem : allCombos(S.size(), SIZE))
    {
        int actualDistance =  std::abs(FIXED - ((S[elem[0] - 1] + S[elem[1] - 1])));
        if(actualDistance < minDistance)//only consider pairs that reduce minDistance
        {
            distancePoints[actualDistance] = std::make_pair(S[elem[0] -1 ], S[elem[1] - 1]);
            minDistance = actualDistance;
        }
    }
    auto citr = distancePoints.cbegin();
    std::cout << "Min distance: " << citr->first << " with numbers " << citr->second.first << " and " << citr->second.second << '\n';
}
int NchooseR( const int& n,  int& r )//// number of combinations of r from n;
{
    if (r > n) return 0;
    if (r * 2 > n) r = n-r;
    if (r == 0) return 1;
    int result = n;
    for( int i = 2; i <= r; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}
std::vector<std::vector<int>> allCombos (const int& n, int r )
{
	int x = NchooseR(n, r);
	std::vector<std::vector<int>> result(x,std::vector<int>(r));
	//2D vector, # inner vectors = number of combinations
	//size of inner vector = 2 (in this case)
	int j {}, k {};
	std::vector<bool> v(n);
    std::fill(v.begin() + n - r, v.end(), true);
    do
    {
        for (int i = 0; i < n; ++i)
        {
            if (v[i])
            {
                result[j][k++] = i + 1;
            }
        }
        k = 0, ++j;
    } while (std::next_permutation(v.begin(), v.end()));
    //some useful links:
    //http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
    //http://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c
    http://en.cppreference.com/w/cpp/algorithm/next_permutation
    return result;
}