# 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.

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.

WLH - WRH = 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.

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.

• I like rule 2, it's flexible but does not allow cheating Commented Jun 10, 2015 at 9:22
• You've basically reinvented the knapsack problem. en.wikipedia.org/wiki/Knapsack_problem Commented Jun 14, 2015 at 0:31
• Thank you @Sparr I am wicked smaat (not really) Commented Jun 15, 2015 at 15:51
• This problem is far too practical and realistic for this site. Commented Nov 18, 2017 at 3:00

# 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.

• The answer by the OP only prints the bags in one hand, so congrats on your 9 byte solution. Commented Jun 13, 2015 at 3:11
• Your write is bugged for input [7 7 7 10 11] Traceback (most recent call last): File "pyth.py", line 772, in <module> File "<string>", line 4, in <module> File "/app/macros.py", line 865, in order TypeError: unorderable types: int() < list()
– user58988
Commented Nov 17, 2017 at 10:02
• @RosLuP This worked at the time, I changed something about s that made it stop working. People didn't like the change, and your comment was the final push I needed to change it back. Commented Nov 18, 2017 at 1:56
• In the commented code it should not be "subset of Q" but "sublist of Q"
– user58988
Commented Nov 18, 2017 at 10:02
• @RosLuP I disagree - a sublist is typically contiguous. Subset and subsequence are two terms for this kind of thing. Commented Nov 18, 2017 at 11:25

# 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.

• This is a very impressive solution - it's not obvious at all that it won't give faulty answers like [[2], [1], [1]], but I think it works, due to exactly how ./ works. Commented Jun 10, 2015 at 1:24
• Actually, I think this fails on cases where everything goes in one hand, like when there's only 1 object. Commented Jun 10, 2015 at 1:28
• @isaacg I had kind of assumed 1 object wasn't valid, as you clearly had to just hold it in one hand. I wouldn't really know what to return for that, [[x], []]? Commented Jun 10, 2015 at 1:31
• I guess so - it's probably OK unless OP says otherwise. Commented Jun 10, 2015 at 1:35
• @isaacg I've posted an answer below. It gives the correct answer for 1 element (I had to add one more byte to the code) Commented Jun 10, 2015 at 2:21

# 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.

• I think :*...W= should work. Commented Jun 10, 2015 at 18:52
• @jimmy23013: Thanks! That made my answer a whole lot more interesting. Commented Jun 10, 2015 at 19:10

# 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 Wone hand = Total weight
Wone 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).

• You could save one byte by doing from itertools import* Commented Jun 10, 2015 at 21:05

# 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=[]);
}

// Test

// Redefine alert to avoid that annoying popup when testing

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>

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.

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. • @WillNess They are all in prelude in the current version. – xnor Commented Sep 17, 2016 at 18:51 • BTW the following point-free code works at the GHCi prompt: snd.minimum.map((,)=<<abs.sum).mapM(\x->[x,-x]). It's 47 bytes. (though I do have an older version installed...) Commented Sep 17, 2016 at 22:30 # 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


# 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


# 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


weight <- function(input) {
mid <- sum(input)/2
n <- 100
input_Length <- length(input)
for(i in 1:n){
idx <- sample(1:input_Length, input_Length)