myaw's blog

By myaw, history, 4 years ago, In English,

The problem look like this : we have n object each object have a weight .

We want to create 2 groups of these objects so the number of objects on the two groups must not differ by more than 1 and the total weight of the objects on each group should be as nearly equal as possible.

examples :

n = 4 : 1 2 3 4 => ans : 5 5

n = 4 : 1 2 3 11111 => ans : 5 11112

n = 3 : 100 90 200 => ans :190 200

my code works fine for small input how ever it gives negative values for large input (n >= 25 ) . My code

You should now that n<=100 and the sum of weights is <= 1e6 .

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

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

memo array size

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

    Nothing wrong with memo size , i increased it and still got WA .

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

      you asked how it gives negatives actually, and not how to solve it. But since you still getting WA (todo: since 100002 gives WA anyway, reduce it to 1 element), then array size must be good — that is simple logic, right? Sorry about my suggestion and please ignore my comment + that below in such case.

      "You should now that n<=100 and the sum of weights is <= 1e6" + line 8. ll memo[100002]; 100002 <= 1e6, and sum of weights <= 1e6, .... ?? sum of weights <= 100002 ?? SOLID

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

Try to make the array memo with bigger size beacause the maximum sum that is possible is 1e8 but yout memo has only 1e6. :D

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    No i said it's guarantee that the sum of all weights will not exceed 1e6 .