You are not logged in. Please login at www.codechef.com to post your questions!

×

Split array into two subsets with minimum difference

Given an array containing N numbers, we need to split the array into two subsets, such that each subset contains N/2 numbers, and the difference between the sum of the two subsets is minimised. I was able to come up with this :

A[i][j][k] = 1 if there is a subset of size 'k' of the first 'i' elements that has sum 'j'. Fill this, and then check A[N][j][N/2] for all j and pick whichever minimises the difference. I want to know if there is a faster way of doing this.

asked 23 Aug '17, 00:43

hemanth_1's gravatar image

6★hemanth_1
1.3k9
accept rate: 25%

Sorry ,i know its a bit late to ask,bt can u tell the constraint for n,a[i]?(assuming a is array)

(03 Apr, 19:25) vivek_19982995★

This question was asked in an interview, the interviewer didn't mention any constraints.

(11 Apr, 23:44) hemanth_16★

Sort array in decreasing order. create 2 array of n/2 max size. insert element into those array using below condition.

for element in array:
    if sum(array1)<=sum(array2):
        if array1 is not full:
            array1.append(element)
        else:
            array2.append(element)
    else:
        if array2 is not full:
            array2.append(element)
        else:
            array1.append(element)

for maximum cases it will give you correct result and for other will give close result.

Another method is to try for all possible combination which is, of course, very slow.

link

answered 03 Apr, 17:21

surya_singh_'s gravatar image

0★surya_singh_
111
accept rate: 0%

I think a greedy approach might work, though I dont know any proof. Start picking elements one by one. Keep track of the difference sum sa, sb for 2 sets A and B. Now put a element in first set if it minimizes |sa-sb| else put it in the other set.

link

answered 23 Aug '17, 14:55

rajarshi_basu's gravatar image

5★rajarshi_basu
4676
accept rate: 10%

2

That would probably give different solutions for different orderings of the input array. I tried taking the numbers in the sorted order and then doing exactly what you mentioned, but it doesn't work (try {1,2,3,4} as the input) :/ what seems to be minimising the difference at some point might not be optimal overall.

(23 Aug '17, 18:52) hemanth_16★

It may be done like this each time either pick the element or not and do this until you have N/2 elements and when you have picked N/2 elements then do this ans = min( ans, (sum_of_N_elems - sum_of_cur_N/2_elems) ). With this method you have to traverse many paths and complexity will be high so you can use dynamic programming to reduce complexity.

link

answered 26 Aug '17, 15:45

visha_l's gravatar image

2★visha_l
11
accept rate: 0%

edited 26 Aug '17, 15:48

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,612
×667
×26

question asked: 23 Aug '17, 00:43

question was seen: 859 times

last updated: 11 Apr, 23:44