I am curious to know if there is an algorithm that, given an array of decimals and integers, and given an integer, returns a sequence in descending order, composed of those numbers of the input array whose sum is as close as possible to the number of input, or even be identical, but not greater.

I wonder if there is something similar, and I wonder if it also has a name, this algorithm.

Thanks in advance!

  • $\begingroup$ It would help comprehension if you give actual names to the algorithm's parameters (even if it is just $k$, $m$, $n$, etc.). $\endgroup$ – dkaeae Aug 26 '19 at 11:56
  • $\begingroup$ In practice, @DeBunkeD's answer was what I was looking for... $\endgroup$ – Memmo Aug 27 '19 at 6:22

There are two famous problems that are similar to what you're looking for. Yours comes closest to the subset sum problem https://en.wikipedia.org/wiki/Subset_sum_problem.

Similarly we have the knapsack problem which revolves around the same idea with the general restriction that items have specific values which should also be taken into account. https://en.wikipedia.org/wiki/Knapsack_problem

Since any integer can be represented as a decimal number your problem can be transformed into either of these problems. In the case of the knapsack problem you would simply set the value of each item to its decimal value.

Both of these problems are NP-complete which means that the only way to calculate the actual maximal achievable value (at the moment) is brute force, although there are pseudopolynomial dynamic programming approaches.

The fact that the output seemingly needs to be ordered is unimportant; there are some very efficient sorting algorithms out there.

| cite | improve this answer | |
  • $\begingroup$ Can some numbers in the input array be repeated to fill the knapsack? $\endgroup$ – Memmo Aug 27 '19 at 6:30
  • $\begingroup$ Depends on your implementation/specification of the problem. The most famous knapsack problem is 0-1 (meaning 0 or 1 occurences of each item), but there are also variations with reuse. $\endgroup$ – DeBunkeD Aug 27 '19 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.