Skip to main content
3 of 3
added 460 characters in body
Dennis
  • 210.6k
  • 41
  • 370
  • 825

CJam, 19 18 bytes

{S+m!{S/1fb:*}$W=}

This is an anonymous function that pops an array of integers from the stack and returns an array of integers separated by a space.

Thanks to @jimmy23013 for his ingenious :* trick, which saved 1 byte.

Try it online in the CJam interpreter.

How it works

S+    e# Append a space to the array of integers.
m!    e# Push the array of all possible permutations.
{     e# Sort the array by the following:
  S/  e#   Split the array at the space.
  1fb e#   Add the integers in each chunk (using base 1 conversion).
  :*  e#   Push the product of both sums.
}$    e# Permutations with a higher product will come last.
W=    e# Select the last permutation.

Denote the total weight of the shopping bags with W. Then, if the bags in one of the hands weigh W/2 - D/2, those in the other hand must weigh and W - (W/2 - D/2) = W/2 + D/2.

We are trying to minimize the difference D. But (W/2 - D/2)(W/2 + D/2) = W^2/4 - D^2/4, which becomes larger as D becomes smaller.

Thus, the maximal product corresponds to the minimal difference.

Dennis
  • 210.6k
  • 41
  • 370
  • 825