'Is there a known algorithm for finding which K elements out of N elements have a sum that is closest to a whole number?

As a small example, say I have N=6 elements

{ 0.03, 0.25000039, 1.391, 500.1, 0.5000001, 1.75001  }

and K=3 then the combination { 0.25000039, 0.5000001, 0.2500001 }, which sums up to 1.00000059 would be the combination that sums up the closest to a whole number.

Is it possible to solve this without "brute force" (iterating through all n choose k elements)?

c++sharp.netalgorithmmathtime-complexity


Solution 1:[1]

I can think of this:

  1. Have a target. Initially target is the number you want to get to.
  2. Select the biggest number smaller than or equal to target.
  3. If there were such a number in previous step reduce the target by that number
  4. If target is zero you are done else go to 2
  5. Else select the smallest number in the series
  6. Reduce the target by that number and check if the absolute value of the target is now bigger than previous target or not if it is you take this last number if it is not you leave it and your current series before the last number is the answer.

Up to here it's giving a close answer. To make it 100% you then repeat the same process this time without the biggest number. Also I omitted this in the algorithm that whenever you want to select a new number if there are no numbers left you are done and that's as close as you can get. Why I left this out is because you might want to allow a number to appear multiple times and therefore you don't need this part.

This is something I came up with. It might need some testing and if you think it's wrong please tell me in the comments. :)

Solution 2:[2]

I guess this task can be reduced to classical Knapsack problem. So the solution as we know it would be NP-complete.

Solution 3:[3]

I had the same problem in one of my projects, where I had to pick a subset of size k out of an original set of size n. The subset should satisfy some constraints and maximize (or minimize) a function calculated on the subset. The problem looks trivial if n is small, but as long as n greater than 30, it starts becoming more challenging given a large number of combinations. Genetic algorithm (GA) is very helpful and practical in this case. For example, you can follow this example, and it will give the result in 1 minute. What you need is to modify the objective function, e.g., out["F"] = (np.sum(self.L[x]) - target)**2. Of course, the GA cannot guarantee an optimal solution, but it should give you at least the near optimal solution quickly.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Emad
Solution 2 Aleksei
Solution 3 andrewJames

Related Questions