bikram28's blog

Finding the maximum sum that can be formed from a set, by partitioning it into two subset

By bikram28, history, 6 years ago, In English

https://stackoverflow.com/questions/29247004/finding-the-maximum-sum-that-can-be-formed-from-a-set-by-partitioning-it-into-t

Given a set of numbers S. Find maximum sum such that Sum(A1) = Sum(A2) Where, A1⊂S and A2⊂S and A1⋂A2=∅ And Sum(X), is the sum of all elements within the set X

in cpp :)

thanks in advance !

test case# 25 elements --> 5 27 24 12 12 2 15 25 32 21 37 29 20 9 24 35 26 8 31 5 25 21 28 3 5 ans=239

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Always provide a source and constraints.

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

    https://stackoverflow.com/questions/29247004/finding-the-maximum-sum-that-can-be-formed-from-a-set-by-partitioning-it-into-t

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

      Let's say that taking an item a to the first set has weight a and value a, while taking it to the second set has weight  - a and value 0. Run a knapsack and find the set with total weight 0 and maximum possible total value.

      In other words, run dp where the dimension is the difference between the total value of items in each set.

      The complexity is O(n·S) where S is the sum of values in the input, so it passes for the provided constraints.

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

        Thanks sir !

        can u plz post the code sir , it will be helpful.

        Errichto

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

          Is some part not clear? Can you implement a standard knapsack?

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

            Yes i can !

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

              Then what is an issue? Why won't you implement this problem yourself and post code here?

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

            sorry but i'm not getting the logic how you implemented with knapsack .

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

              The implementation of knapsack doesn't matter. You can treat it as a blackbox, assuming we allow negative weights.

              And I also provided a description without knapsack ("in other words, ...").

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

        What about the case when an element is not included in any of the sets?

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

          The solution is that every number gave us two items and you are allowed to take at most one of them. In particular, you can take none of them.

          → Reply