2
$\begingroup$

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example: 

A = [1, 2, 3, 4, 6] & K = 2
Maximum Sum Subsequence = 8 = [2, 6] & [1, 3, 4]

If, K = 3 and A = [1, 2, 3, 4, 6, 8, 9]
Maximum Sum Subsequence = 11 = [9, 2] & [8, 3] & [6, 4, 1]

It is not necessary that all the elements of the array need to be a part of the subsequences but each element can only be part of 1 subsequence.

I tried a brute force approach with Knapsack but that doesnt work. Any better approaches or optimizations?

Improve this question
$\endgroup$
1
  • $\begingroup$ Rather than answering in the comments, please edit the question to make it clear, so that people who read the question can understand the problem without having to read the comments. Thank you. $\endgroup$
    – D.W. ♦
    Commented Sep 10, 2018 at 17:29

1 Answer 1

Reset to default
3
$\begingroup$

This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$.

Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making $S' = S \cup \{x, x - n\}$ for some sufficiently large $x$ and solving your problem to find the $K = 2$ maximum equal subsequence sums. Then iff the answer includes $x$ and $x - n$ there is a subset that sums to $n$ and we efficiently solved the given subset sum problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ What is 'n' here? Could you please elaborate more on your approach? $\endgroup$
    – user248884
    Commented Sep 11, 2018 at 6:18
  • $\begingroup$ @user248884 $n$ is defined in the first sentence. I don't know what exactly is unclear for me to elaborate on. $\endgroup$
    – orlp
    Commented Sep 11, 2018 at 6:24
  • $\begingroup$ Consider a case where A = [1,2,3,4,6,8,9] & $K$ = 3. Applying subset sum, we get that 1,2,3,4 can be part of the subsequence, so K = 1. For the next iteration, we remove 1,2,3,4 from the array so A = [6,8,9]. This returns false as a subsequence of 10 cannot be made. But, infact the subsequence of 10 is possible (Eg: [1,9], [2, 8], [4,6]) if the elements were sampled differently. I wanted elaboration on such cases. Sorry for not making it clear earlier. $\endgroup$
    – user248884
    Commented Sep 11, 2018 at 7:40
  • 1
    $\begingroup$ @user248884 You misunderstand what my argument's purpose is. It shows that if an efficient algorithm for your problem existed, you could use it to solve the given subset sum problem, which is NP-complete. This means that your problem is NP-hard and thus to our best possible knowledge no polynomial time algorithm exists. The direction of my argument is from given subset sum to your problem, to show you could solve this hard problem with an algorithm that works for your problem. $\endgroup$
    – orlp
    Commented Sep 11, 2018 at 9:53

Your Answer

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

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