CODEWITHSUNDEEP
c++arraysalgorithmstl
user2256798
user2256798

Reputation:

Split Array into two sets?

I have an array W of 0..N-1

I need to split them into two sets: Say K and N-K elements.

But the condition is: sum(N-K) - sum(K) should be maximum.

How do I approach this?

I tried doing this: Sort the array - std::sort(W,W+N), and then:

for(int i=0; i<K; ++i) less+=W[i];
for(int i=K; i<N; ++i) more+=W[i];

And then more-less

But I don't think this is the optimum way, or it may even be wrong for some of the cases.

Thanks.

UPDATE:

We have to choose K elements from W such that difference betweensum(k elements) and sum(remaining elements) is maximum.

Upvotes: 2

Views: 922

Answers (3)

Drew Dormann
Drew Dormann

Reputation: 63755

Edit: Note that in your posted question, you seem to be expecting sort to sort from high-to-low. Both std::sort and std::nth_element put the low elements first. I have replaced K with (N-K) in the answer below to correct that.

Edit after UPDATE: Do the below twice, once for K and once for (N-K). Choose the optimal answer.

More optimal than std::sort would be std::nth_element for your purposes.

std::nth_element( W, W+(N-K), W+N );

Your use of std::sort will use O(n log n) complexity to order all the elements within both your sets, which you don't need.

std::nth_element will use O(n) complexity to partition without completely sorting.

Note: your for loops may also be replaced with std::accumulate

less = std::accumulate( W, W+(N-K), 0 );
more = std::accumulate( W+(N-K), W+N, 0 );

Upvotes: 2

dejavu
dejavu

Reputation: 3254

It can be done using max heap. O(n + n log k) time

Make a max heap of size k. We have find the lowest k elements of the array. The root of heap will be the highest element in the heap. Make a heap of first k elements.

Now iterate through the array. Compare the array element with the root of max heap. If it is smaller than root then replace it and heapify the heap again. This will take O(n log k) time. Find the sum of elements of heap.

Now you can find the sum of rest of the elements of array and get the difference. (O(n)) time

Total time O(n + n log k)

EDIT: Perhaps you can find the sum of all elements of array while traversing it for heap. This will save O(n) time and it can be solved in O(n log k)

Upvotes: 0

quetzalcoatl
quetzalcoatl

Reputation: 33506

You are to split the set of elements into two distinctive nonoverlapping subsets A and B. You want the sum(A)-sum(B) be as high as possible.

Therefore, you want the sum(A) be as high as possible and sum(B) as low as possible.

Therefore, the set 'A' should contain as high elements as possible
and the set 'B' should contain as low elements as possible

By sorting the input set by element's value, and by assigning 'lowest elements' to B and 'highest elements' to A, you are guaranteed that the sum(A)-sum(B) will be max possible.

I do not see any cases where your approach would be wrong.

As to the 'being optimal' things, I did not analyze it at all. Drew's note seems quite probable.

Upvotes: 2

Related Questions