1
$\begingroup$

I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums).

Attempt at solving :

I have been looking at ordering the sums starting with the unbounded knapsack problem (UKP) with equal weights to find the sets of each size with minimal sum, then establishing a rule for determining the order of corresponding sets after replacing elements, in the hope that this would reduce the number of comparisons. However, this doesn't seem to simplify the problem.

Improve this question
$\endgroup$
4
  • $\begingroup$ math.stackexchange.com/questions/89419/… $\endgroup$
    – Yuval Filmus
    Dec 7, 2020 at 22:03
  • $\begingroup$ Thank you for that reference. It does accomplish what I'm looking for, but I can't reach large values in the search space with that speed. Is there any chance I could skip over a chunk of subsets without explicitly finding and summing them? $\endgroup$
    – dripset_pushbert
    Dec 7, 2020 at 22:21
  • 1
    $\begingroup$ The problem is NP-hard: if we could solve your problem efficiently, it would be easy to solve the subset sum problem too (using binary search). I don't know whether there is a way to take advantage of the known algorithms for subset sum to solve this for the a multiset of size 100; I haven't figured out a way, but maybe someone else will have some ideas. $\endgroup$
    – D.W. ♦
    Dec 8, 2020 at 0:00
  • $\begingroup$ I see, you have clarified the relation between my problem and subset sum and a lower bound on time complexity is already very good to know, thank you. $\endgroup$
    – dripset_pushbert
    Dec 8, 2020 at 0:06

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.