Help me carry my shopping bags

Question

It was a warm summer evening...

when my stupid car decided to break down in the middle of the road on my way back from the supermarket. I pushed it to the sideline and decided to walk home. I opened the trunk to take out the grocery and remaining stuff. It was then that I noticed the items were not evenly bagged. Some bags had more heavy items while others had few lighter stuff - some even had a mix of such items. To make it easy for me to carry, I decided to group everything in to two bags and make their weights as close to each other as possible.

Your goal

is to help me rearrange the items in to two shopping bags in such a way that the difference between both bags is close to zero as possible.
Mathematically:

WEIGHT _{LEFT HAND} — WEIGHT _{RIGHT HAND} ≈ 0

Example

If I had only 2 items, Bread and Peanut butter, and the weight of bread is 250 grams and peanut butter is 150 grams, the best way is to carry them separately in two hands.

W_LH - W_RH = W_(BREAD) - W_(P.BUTTER)
250 - 150 = 100

The other possibility is :

W_{(BREAD, P.BUTTER)} - W_{(empty hand)} = (250 + 150) - 0 = 400

This is not better than our first case, so you should go with the first one.

Your code should

1. take inputs of numbers indicating weights of items in the shopping bag. Units are not important, but they should be the same (ideally kilograms or grams). Input can be done one by one or all at once. You may restrict the total count to 20 items max, if you want.
2. The input format/type is up to you to choose, but nothing else should be present other than the weights.
3. Any language is allowed, but stick to standard libraries.
4. Display output. Again, you're free to choose the format, but explain the format in your post. ie, how can we tell which ones are left hand items and which ones are right hand items.

Points

1. Shortest code wins.

Hint

The two possible algorithms that I could think of are differentiation (faster) and permutations/combinations (slower). You may use these or any other algorithm that does the job.

Answer 1

Pyth, 9 bytes

ehc2osNyQ

Input, output formats:

Input:
[1, 2, 3, 4, 5]
Output:
[1, 2, 4]

Demonstration.

ehc2osNyQ
             Q = eval(input())
       yQ    Take all subsets of Q.
    osN      Order those element lists by their sums.
  c2         Cut the list in half.
eh           Take the last element of the first half.

This works because y returns the subsets in such an order that each subset and its complement are equidistant fom the center. Since the sum of a subset and the sum of its complement will always be equidistant from the center, the list after osNyQ will also have this property. Thus, the center two elements of osNyQ are complements, and must have an optimal split. We extract the first of those two elements and print it.

Answer 2

Pyth, 16

ho.a-FsMNs./M.pQ

This takes the inputs as a pythonic list on STDIN. The output is a list of 2 lists with the first list being the items in one bag, and the second list representing the items in the second bag. This brute forces all combinations, so it will run very slowly (or run out of memory) for large inputs.

Try it online here

To support the handling of just one input, this goes up to 17:

hho.a-FsMNs./M.pQ

This will print the values that go in one hand.

Answer 3

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.

Answer 4

Python 2.7, 161, 160

code

from itertools import*
m=input();h=sum(m)/2.;d=h
for r in(c for o in range(len(m)+1) for c in combinations(m,o)):
 t=abs(h-sum(r))
 if t<=d:d=t;a=r
print a

Algorithm

2 x W_{one hand} = Total weight
W_{one hand} ~ Total weight / 2

Check if each combination is getting closer to half of total weight. Iterate and find the best one.

input

>>>[1,2,3,4]

output

(2, 3)

The displayed tuple goes in one hand, the ones that are not displayed goes in the other (it is not against the rules).

Answer 5

JavaScript (ES6) 117

Using a bit mask to try every possible split, so it is limited to 31 items (ok with the rules). Like the ref answer it outputs just one hand. Note: i look for the minimum difference >=0 to avoid Math.abs, as for each min < 0 there is another > 0, just swapping hands.

To test: run the snippet in Firefox, input a list of numbers comma or space separated.

f=(l,n)=>{ // the unused parameter n is inited to 'undefined'
  for(i=0;++i<1<<l.length;t<0|t>=n||(r=a,n=t))
    l.map(v=>(t+=i&m?(a.push(v),v):-v,m+=m),m=1,t=0,a=[]);
  alert(r)
}

// Test

// Redefine alert to avoid that annoying popup when testing
alert=x=>O.innerHTML+=x+'\n';

go=_=>{
  var list=I.value.match(/\d+/g).map(x=>+x); // get input and convert to numbers
  O.innerHTML += list+' -> ';
  f(list);
}

#I { width: 300px }

<input id=I value='7 7 7 10 11'><button onclick='go()'>-></button>

<pre id=O></pre>

Answer 6

Haskell, 73 bytes

import Data.List
f l=snd$minimum[(abs$sum l-2*sum s,s)|s<-subsequences l]

Outputs a list of items in one hand. The missing elements go to the other hand.

Usage: f [7,7,7,10,11] -> [7,7,7]

For all subsequences s of the input list l calculate the absolute value of the weight difference between s and the missing elements of l. Find the minimum.

Answer 7

Haskell, 51 bytes

f l=snd$minimum$((,)=<<abs.sum)<$>mapM(\x->[x,-x])l

Output format is that left-hand weights are positive and right-hand weights are negative.

>> f [2,1,5,4,7]
[-2,-1,5,4,-7]

To generate every possible split, we use mapM(\x->[x,-x])l to negate every possible subset of elements. Then, ((,)=<<abs.sum) labels each one with its absolute sum and snd$minimum$((,)=<<abs.sum) take the smallest-labeled element.

I couldn't get it point-free because of type-checking issues.

Answer 8

Axiom, 292 bytes

R==>reduce;F(b,c)==>for i in 1..#b repeat c;p(a)==(#a=0=>[a];w:=a.1;s:=p delete(a,1);v:=copy s;F(s,s.i:=concat([w],s.i));concat(v,s));m(a)==(#a=0=>[[0],a];#a=1=>[a,a];b:=p(a);r:=[a.1];v:=R(+,a)quo 2;m:=abs(v-a.1);F(b,(b.i=[]=>1;d:=abs(v-R(+,b.i));d<m=>(m:=d;r:=copy b.i);m=0=>break));[[m],r])

A brute force application. This would minimize the set

A={abs(reduce(+,a)quo 2-reduce(+,x))|x in powerSet(a)}

because if is minimum

y=min(A)=abs(reduce(+,a)quo 2-reduce(+,r))

it would be minimum too

2*y=abs(reduce(+,a)-2*reduce(+,r))=abs((reduce(+,a)-reduce(+,r))-reduce(+,r)) 

where (reduce(+,a)-reduce(+,r)) and reduce(+,r) are the 2 weight of two bags.( But that last formula not find to me the minimum, in the application). Ungolf and results

-- Return the PowerSet or the Powerlist of a
powerSet(a)==
    #a=0=>[a]
    p:=a.1;s:=powerSet delete(a,1);v:=copy s
    for i in 1..#s repeat s.i:=concat([p],s.i)
    concat(v,s)

-- Return one [[m], r] where
-- r is one set or list with reduce(+,r)=min{abs(reduce(+,a)quo 2-reudece(+,x))|x in powerSet(a)}
-- and m=abs(reduce(+,a) quo 2-reduce(+,r))
-- because each of two part, has to have the same weight
MinDiff(a)==
    #a=0=>[[0],a]
    #a=1=>[ a ,a]
    b:=powerSet(a)
    r:=[a.1];v:=reduce(+,a) quo 2;m:=abs(v-a.1)
    for i in 1..#b repeat
        b.i=[]=>1
        k:=reduce(+,b.i)
        d:=abs(v-k)
        d<m=>(m:=d;r:=copy b.i)
        m=0=>break
    [[m],r]

--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

(5) -> a:=randList(12,1,10000)
   (5)  [8723,1014,2085,5498,2855,1121,9834,326,7416,6025,4852,7905]
                                                       Type: List Integer
(6) -> m(a)
   (6)  [[1],[1014,2085,5498,1121,326,6025,4852,7905]]
                                                  Type: List List Integer
(7) -> x:=reduce(+,m(a).2);[x,reduce(+,a)-x]
   (7)  [28826,28828]
                                               Type: List PositiveInteger
(8) -> m([1,2,3,4])
   (8)  [[0],[2,3]]
                                                  Type: List List Integer
(9) -> m([10,1,2,3,4])
   (9)  [[0],[10]]
                                                  Type: List List Integer
(10) -> m([40,20,80,50,100,33,2])
   (10)  [[0],[40,20,100,2]]
                                                  Type: List List Integer
(11) -> m([7,7,7,10,11])
   (11)  [[0],[10,11]]
                                                  Type: List List Integer

Answer 9

Vyxal, 7 bytes

ṗµ∑;Iht

Try it Online!

Port of isaacg's Pyth answer, go upvote that

ṗ       # Subsets
 µ∑;    # Sorted by sum
    I   # Cut in half
     ht # Get the second element of the first half

Answer 10

R (234)

a longer and slower solution with R.

Function:

function(p){m=sum(p)/2;n=100;L=length(p);a=matrix(0,n,L+2);for(i in 1:n){idx=sample(1:L,L);a[i,1:L]=idx;j=1;while(sum(p[idx[1:j]])<=m){a[i,L+1]=abs(sum(p[idx[1:j]])-m);a[i,L+2]=j;j=j+1}};b=which.min(a[,L+1]);print(p[a[b,1:a[b,L+2]]])}

Expected input - vector with the weights.
Expected output - vector with the weights for one hand.

Example

> Weight(c(1,2,3,4))
[1] 3 2
> Weight(c(10,1,2,3,4))
[1] 10
> Weight(c(40,20,80,50,100,33,2))
[1] 100  40  20  2
> Weight(c(7,7,7,10,11))
[1] 7 7 7

Human readable code version:

weight <- function(input) {
  mid <- sum(input)/2
  n <- 100
  input_Length <- length(input)
  answers <- matrix(0, n, input_Length+2)
  for(i in 1:n){
    idx <- sample(1:input_Length, input_Length)
    answers[i, 1:input_Length ] <- idx
    j <- 1
    while(sum(input[idx[1:j]]) <= mid){
        answers[i, input_Length+1] <- abs(sum(input[idx[1:j]]) - mid)
        answers[i, input_Length+2] <- j
        j <- j + 1
    }
  }
  best_line <- which.min(answers[, input_Length+1])
  print(paste("weight diference: ", answers[best_line, input_Length+1]))
  print(input[answers[best_line, 1:answers[best_line, input_Length+2]]])
}