### Death_Scythe's blog

By Death_Scythe, history, 8 years ago,

Hi all!

I don't have the exact problem statement, it was asked in one of the coding tests for an interview but I think I remember the problem quite well.

Given an array of n values, we have to make two sets such that size of first is at most k and size of second is at most s. The difference of sum of values in first set and sum of values in second set is minimum. I need to find this minimum value.

The sets must be non-empty.

Constraints: n<=200, k,s<=100, 0<values in array<=1000

Please let me know if something is unclear.

Thanks!

• -1

 » 8 years ago, # |   0 Can they have common elements?
•  » » 8 years ago, # ^ |   0 No. :)
 » 8 years ago, # | ← Rev. 2 →   +11 for every element try to put it in the first set if cur_size_of_first_set+1 <= k or put it in the second set if cur_size_of_second_set+1 <= s and check the difference in every step .. your statue is dp[pos][difference][cur_size_of_first_set_size][cur_size_of_second_set_size] I think this approach will work but I don't know if the complexity is good or if we can do any optimization on it !
•  » » 8 years ago, # ^ |   -11 I don't think this would work. How do you perform the transition between the states?
•  » » » 8 years ago, # ^ | ← Rev. 4 →   +1 for every element :1- try to add it to the first set if cur_size_of_first_set+1 <= k and the size of the first set will be increase by one2- try to add it to the second set if cur_size_of_second_set+1 <= s and the size of the second set will be increase by one3- ignore it and the size of the tow set won't changeand after each step assume that it's the optimal division and check the difference
•  » » » » 8 years ago, # ^ |   -10 The problem is calculating the difference. Can you please elaborate on how do you find the new difference?
•  » » » » » 8 years ago, # ^ |   +1 you need to find the differences for each set or the |sum_in_the_first_set — sum_in_the_second_set| ?
•  » » » » » » 8 years ago, # ^ |   +1 The latter. "|sum_in_the_first_set — sum_in_the_second_set|"
•  » » 8 years ago, # ^ |   +1 You can eliminate one dimension of your DP by setting dp[pos][difference][size_of_first_set] to be the smallest possible second set size that achieves this difference (since smaller is always better). Not sure if it still can be optimized more.
•  » » » 8 years ago, # ^ |   -10 Hi ffao!How do you set up the recurrence here? Sorry if this is a stupid question but I really don't see how to go from one state to the other.
 » 8 years ago, # |   0 Auto comment: topic has been updated by Death_Scythe (previous revision, new revision, compare).