Death_Scythe's blog

Dividing an array into two sets with minimum difference
By Death_Scythe, history, 8 years ago, In English

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!

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can they have common elements?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

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 !

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I don't think this would work. How do you perform the transition between the states?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +1 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it -10 Vote: I do not like it

        The problem is calculating the difference. Can you please elaborate on how do you find the new difference?

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          you need to find the differences for each set or the |sum_in_the_first_set — sum_in_the_second_set| ?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            The latter. "|sum_in_the_first_set — sum_in_the_second_set|"

            → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Death_Scythe (previous revision, new revision, compare).

→ Reply