tsminh_3's blog

Divide into two group
By tsminh_3, history, 9 years ago, In English 
Please help me with this 

Give n ropes, each rope in length a[i] (n<=10^3). Then divide them into two group
- Sum1 = sum of all ropes in group 1
- Sum2 = sum of all ropes in group 2 
The task asked if there is a way to divide them into two group which S1=S2`
Note : the numbers of rope in each group maybe not equal to the other

Sorry for my bad at English :(
  • Vote: I like it
  • -21
  • Vote: I do not like it

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

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

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

What is the size of array a?

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

sum all the elements of the array . if sum is odd print no otherwise find subset sum of sum/2 if this exist . B-)

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

    He has mentioned a[i] <= 10^9. You cannot solve the problem.

    → Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can you please give me the link of this question?

→ Reply
»
9 years ago, # |
  Vote: I like it +19 Vote: I do not like it

According to Wiki Link , this problem is NP-complete and has pseudo-polynomial (O(n*sum)) time dp solution which is feasible only when sum is small. Hence, it would be nice if you could give a link to problem so that people can verify that your description and/or constraints about the problem are accurate.

→ Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This is basically the subset sum problem, and it's NP-complete, so you can't expect to solve it in polynomial time. If values were smaller (maybe  ≤ 105), you could do DP.

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

    Please can you explain how to do a DP for a[i] <  = 105 ?

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

      At every step just update all possible sums you can reach if you added current element or if you subtracted current element. If after the last element you could have reached 0 then it is possible to split the set into 2 parts.

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

        I still don't understand it. Would you do the updates using a map/set ? Wouldn't the total possible sums for a[i] <  = 105, n <  = 103 be 108 and storing them in a map would cause the program to exceed memory limit for sure.

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

          Yes, I mean the total sum of elements  ≤ 105...

          → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
          ← Rev. 7   Vote: I like it 0 Vote: I do not like it

          For i elements the total possible sums can be i * (i + 1) / 2 if the array is of numbers sequentially like 1,2,3.. and so on so it would atleast get a TLE as time taken could be and this is not even the worst case.

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

      Let A be the array and DP[i][j] the DP matrix. DP[i][j] is true if it is possible to have a sum of j by taking some elements from the first i elements.

      At every state, you can either add the next element or not, so from a valid state DP[i][j] we can get either to DP[i + 1][j] (do not take the next element) or to DP[i + 1][j + Ai + 1] (take the next element).

      If S is the sum of all elements and is true, then you can divide the array into two parts with equal sum.

      → Reply