Es war ein warmer Sommerabend ...

Als mein dummes Auto beschloss, auf dem Rückweg vom Supermarkt mitten auf der Straße eine Panne zu haben. Ich schob es an die Seitenlinie und beschloss, nach Hause zu gehen. Ich öffnete den Kofferraum, um das Lebensmittelgeschäft und die restlichen Sachen herauszunehmen. Zu diesem Zeitpunkt bemerkte ich, dass die Artikel nicht gleichmäßig verpackt waren. Einige Taschen hatten schwerere Gegenstände, andere hatten weniger leichtere Sachen - einige hatten sogar eine Mischung aus solchen Gegenständen. Um mir das Tragen zu erleichtern, habe ich beschlossen, alles in zwei Säcke zu gruppieren und die Gewichte so nah wie möglich aneinander zu bringen.

Dein Ziel

soll mir helfen, die Artikel in zwei Einkaufstaschen so zu ordnen, dass der Unterschied zwischen beiden Taschen so nahe wie möglich bei Null liegt.
Mathematisch:

GEWICHT _{LINKE HAND} - GEWICHT RECHTE _HAND ≈ 0

Beispiel

Wenn ich nur 2 Artikel hatte, Brot und Erdnussbutter, und das Gewicht von Brot beträgt 250 Gramm und Erdnussbutter 150 Gramm, ist der beste Weg, sie separat in zwei Händen zu tragen.

W _LH - W _RH = W _(BROT) - W _{(P. BUTTER)}
250 - 150 = 100

Die andere Möglichkeit ist:

W _{(BROT, P. BUTTER)} - W _{(leere Hand)} = (250 + 150) - 0 = 400

Dies ist nicht besser als unser erster Fall, deshalb sollten Sie den ersten Fall wählen.

Ihr Code sollte

1. Geben Sie Zahlen ein, die das Gewicht der Artikel in der Einkaufstasche angeben. Einheiten sind nicht wichtig, sollten aber gleich sein (idealerweise Kilogramm oder Gramm). Die Eingabe kann einzeln oder alle gleichzeitig erfolgen. Sie können die Gesamtanzahl auf maximal 20 Elemente beschränken, wenn Sie möchten.
2. Das Eingabeformat / der Eingabetyp können Sie selbst auswählen, es sollte jedoch nichts anderes als die Gewichte vorhanden sein.
3. Jede Sprache ist erlaubt, aber halte dich an Standardbibliotheken.
4. Ausgabe anzeigen. Auch hier können Sie das Format frei wählen, aber das Format in Ihrem Beitrag erläutern. dh wie können wir erkennen, welche Gegenstände für die linke Hand und welche für die rechte Hand sind.

Punkte

1. Kürzester Code gewinnt.

Hinweis

Die beiden möglichen Algorithmen, die ich mir vorstellen könnte, sind Differenzierung (schneller) und Permutationen / Kombinationen (langsamer). Sie können diesen oder einen anderen Algorithmus verwenden, der die Aufgabe erfüllt.

Pyth, 9 Bytes

ehc2osNyQ

Eingabe-, Ausgabeformate:

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.

Dies funktioniert, weil ydie Teilmengen in einer solchen Reihenfolge zurückgegeben werden, dass jede Teilmenge und ihr Komplement gleich weit vom Zentrum entfernt sind. Da die Summe einer Teilmenge und die Summe ihres Komplements immer gleich weit vom Zentrum entfernt sind, hat auch die nachfolgende Liste osNyQdiese Eigenschaft. Somit sind die beiden mittleren Elemente osNyQKomplemente und müssen eine optimale Aufteilung aufweisen. Wir extrahieren das erste dieser beiden Elemente und drucken es aus.

Pyth, 16

ho.a-FsMNs./M.pQ

Dadurch werden die Eingaben als Python-Liste in STDIN übernommen. Die Ausgabe ist eine Liste von 2 Listen, wobei die erste Liste die Artikel in einem Beutel darstellt und die zweite Liste die Artikel im zweiten Beutel darstellt. Dieser Brute erzwingt alle Kombinationen, daher wird er bei großen Eingaben sehr langsam ausgeführt (oder es geht ihm der Speicher aus).

Probieren Sie es hier online aus

Um die Behandlung von nur einer Eingabe zu unterstützen, sind dies bis zu 17:

hho.a-FsMNs./M.pQ

Dadurch werden die Werte gedruckt, die in einer Hand liegen.

CJam, 19 18 Bytes

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

Dies ist eine anonyme Funktion, die ein Array von Ganzzahlen aus dem Stapel löscht und ein durch ein Leerzeichen getrenntes Array von Ganzzahlen zurückgibt.

Vielen Dank an @ jimmy23013 für seinen genialen :*Trick, der 1 Byte eingespart hat.

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

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.

Geben Sie das Gesamtgewicht der Einkaufstaschen mit W an . Wenn dann die Beutel in einer der Hände W / 2 - D / 2 wiegen , müssen die in der anderen Hand wiegen und W - (W / 2 - D / 2) = W / 2 + D / 2 .

Wir versuchen den Unterschied D zu minimieren . Aber (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , was größer wird, wenn D kleiner wird.

Das maximale Produkt entspricht also der minimalen Differenz.

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

Algorithmus

2 x W _{eine Hand} = Gesamtgewicht
W _{eine Hand} ~ Gesamtgewicht / 2

Überprüfen Sie, ob sich jede Kombination dem halben Gesamtgewicht nähert. Iteriere und finde den besten.

Eingang

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

Ausgabe

(2, 3)

Das angezeigte Tupel geht in die eine Hand, das nicht angezeigte in die andere (es verstößt nicht gegen die Regeln).

JavaScript ( ES6 ) 117

Verwenden Sie eine Bitmaske, um jede mögliche Aufteilung zu versuchen, sodass sie auf 31 Elemente beschränkt ist (gemäß den Regeln in Ordnung). Wie die Antwort gibt es nur eine Hand aus. Hinweis: Ich achte auf die minimale Differenz> = 0, um Math.abs zu vermeiden, da es für jede Minute <0 eine weitere> 0 gibt, bei der nur die Hände getauscht werden.

Zum Testen: Führen Sie das Snippet in Firefox aus, und geben Sie eine Liste mit durch Kommas oder Leerzeichen getrennten Zahlen ein.

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>

Haskell, 73 Bytes

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

Gibt eine Liste von Elementen in einer Hand aus. Die fehlenden Elemente gehen dagegen.

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

Berechnen Sie für alle Teilfolgen sder Eingabeliste lden absoluten Wert der Gewichtsdifferenz zwischen sund den fehlenden Elementen von l. Finde das Minimum.

Haskell, 51 Bytes

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

Das Ausgabeformat ist, dass die Gewichte für die linke Hand positiv und die Gewichte für die rechte Hand negativ sind.

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

Um jeden möglichen Split zu generieren mapM(\x->[x,-x])l, negieren wir jede mögliche Teilmenge von Elementen. Dann ((,)=<<abs.sum)Etikett jeweils mit ihrer absoluten Summe und snd$minimum$((,)=<<abs.sum)nehmen das kleinste markierte Element.

Ich konnte es aufgrund von Problemen mit der Typprüfung nicht ohne weiteres bekommen.

R (234)

eine längere und langsamere Lösung mit R.

Funktion:

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]]])}

Erwartete Eingabe - Vektor mit den Gewichten.
Erwartete Ausgabe - Vektor mit den Gewichten für eine Hand.

Beispiel

> 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

Vom Menschen lesbare Codeversion:

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]]])
}

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])

Eine Brute-Force-Anwendung. Dies würde die Menge minimieren

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

denn wenn ist das Minimum

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

es wäre auch minimal

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

Dabei ist (reduzieren (+, a) -reduzieren (+, r)) und reduzieren (+, r) das Gewicht von zwei Beuteln. Ungolf und Ergebnisse

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