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!
Can they have common elements?
No. :)
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 !I don't think this would work. How do you perform the transition between the states?
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 one
2- 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 one
3- ignore it and the size of the tow set won't change
and after each step assume that it's the optimal division and check the difference
The problem is calculating the difference. Can you please elaborate on how do you find the new difference?
you need to find the differences for each set or the |sum_in_the_first_set — sum_in_the_second_set| ?
The latter. "|sum_in_the_first_set — sum_in_the_second_set|"
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.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.
Auto comment: topic has been updated by Death_Scythe (previous revision, new revision, compare).