Ce fut une chaude soirée d'été ...

quand ma stupide voiture a décidé de tomber en panne au milieu de la route sur le chemin du retour du supermarché. Je l'ai poussé à l'écart et j'ai décidé de rentrer à pied. J'ai ouvert le coffre pour sortir l'épicerie et le reste. C'est alors que j'ai remarqué que les articles n'étaient pas uniformément emballés. Certains sacs avaient des articles plus lourds tandis que d'autres avaient peu de choses plus légères - certains avaient même un mélange de ces articles. Pour me faciliter le transport, j'ai décidé de tout regrouper dans deux sacs et de faire leurs poids le plus près possible les uns des autres.

Ton but

est de m'aider à réorganiser les articles dans deux sacs de manière à ce que la différence entre les deux sacs soit aussi proche que possible de zéro.
Mathématiquement:

POIDS _{MAIN GAUCHE} - POIDS _{MAIN DROITE} ≈ 0

Exemple

Si je n'avais que 2 articles, du pain et du beurre d'arachide, et que le poids du pain est de 250 grammes et que le beurre d'arachide est de 150 grammes, la meilleure façon est de les transporter séparément à deux mains.

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

L'autre possibilité est:

W _{(PAIN, BEURRE)} - W _{(main vide)} = (250 + 150) - 0 = 400

Ce n'est pas mieux que notre premier cas, vous devriez donc opter pour le premier.

Votre code devrait

1. prendre des entrées de nombres indiquant le poids des articles dans le panier. Les unités ne sont pas importantes, mais elles devraient être les mêmes (idéalement des kilogrammes ou des grammes). L'entrée peut être effectuée une par une ou toutes en même temps. Vous pouvez limiter le nombre total à 20 articles maximum, si vous le souhaitez.
2. Le format / type d'entrée est à vous de choisir, mais rien d'autre ne doit être présent autre que les poids.
3. N'importe quelle langue est autorisée, mais respectez les bibliothèques standard.
4. Afficher la sortie. Encore une fois, vous êtes libre de choisir le format, mais expliquez le format dans votre message. c'est-à-dire, comment pouvons-nous savoir lesquels sont des éléments de gauche et lesquels sont des éléments de droite.

Points

1. Le code le plus court gagne.

Allusion

Les deux algorithmes possibles auxquels je pourrais penser sont la différenciation (plus rapide) et les permutations / combinaisons (plus lent). Vous pouvez utiliser ces algorithmes ou tout autre algorithme qui fait le travail.

Pyth, 9 octets

ehc2osNyQ

Formats d'entrée et de sortie:

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

Manifestation.

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.

Cela fonctionne car yrenvoie les sous-ensembles dans un ordre tel que chaque sous-ensemble et son complément sont équidistants du centre. Puisque la somme d'un sous-ensemble et la somme de son complément seront toujours équidistantes du centre, la liste suivante osNyQaura également cette propriété. Ainsi, les deux éléments centraux de osNyQsont complémentaires et doivent avoir une répartition optimale. Nous extrayons le premier de ces deux éléments et l'imprimons.

Pyth, 16

ho.a-FsMNs./M.pQ

Cela prend les entrées comme une liste pythonique sur STDIN. Le résultat est une liste de 2 listes avec la première liste étant les articles dans un sac, et la deuxième liste représentant les articles dans le deuxième sac. Cette brute force toutes les combinaisons, elle s'exécutera donc très lentement (ou manquera de mémoire) pour les entrées volumineuses.

Essayez-le en ligne ici

Pour prendre en charge la gestion d'une seule entrée, cela va jusqu'à 17:

hho.a-FsMNs./M.pQ

Cela imprimera les valeurs qui vont dans une main.

CJam, 19 18 octets

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

Il s'agit d'une fonction anonyme qui extrait un tableau d'entiers de la pile et renvoie un tableau d'entiers séparés par un espace.

Merci à @ jimmy23013 pour son astucieux :*tour qui a sauvé 1 octet.

Essayez-le en ligne dans l' interpréteur CJam .

Comment ça marche

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.

On note le poids total des sacs à provisions avec W . Ensuite, si les sacs d'une des mains pèsent W / 2 - D / 2 , ceux de l'autre main doivent peser et W - (W / 2 - D / 2) = W / 2 + D / 2 .

Nous essayons de minimiser la différence D . Mais (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , qui devient plus grand lorsque D devient plus petit.

Ainsi, le produit maximal correspond à la différence minimale.

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

Algorithme

2 x W d' _{une main} = Poids total
W d' _{une main} ~ Poids total / 2

Vérifiez si chaque combinaison se rapproche de la moitié du poids total. Itérer et trouver le meilleur.

contribution

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

sortie

(2, 3)

Le tuple affiché va dans une main, ceux qui ne sont pas affichés vont dans l'autre (ce n'est pas contraire aux règles).

JavaScript ( ES6 ) 117

Utiliser un masque de bits pour essayer toutes les divisions possibles, il est donc limité à 31 éléments (ok avec les règles). Comme la réponse ref, elle ne produit qu'une seule main. Remarque: je cherche la différence minimale> = 0 pour éviter Math.abs, car pour chaque min <0, il y a un autre> 0, juste en échangeant des mains.

Pour tester: exécutez l'extrait dans Firefox, entrez une liste de nombres séparés par des virgules ou des espaces.

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 octets

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

Affiche une liste d'éléments dans une main. Les éléments manquants vont en revanche.

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

Pour toutes les sous-séquences sde la liste d'entrée, lcalculez la valeur absolue de la différence de poids entre set les éléments manquants de l. Trouvez le minimum.

Haskell, 51 octets

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

Le format de sortie est que les poids à gauche sont positifs et les poids à droite sont négatifs.

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

Pour générer chaque fractionnement possible, nous utilisons mapM(\x->[x,-x])lpour annuler tous les sous-ensembles d'éléments possibles. Ensuite, ((,)=<<abs.sum)étiquetez chacun avec sa somme absolue et snd$minimum$((,)=<<abs.sum)prenez le plus petit élément étiqueté.

Je n'ai pas pu l'obtenir sans point en raison de problèmes de vérification de type.

R (234)

une solution plus longue et plus lente avec R.

Une fonction:

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

Entrée attendue - vecteur avec les poids.
Sortie attendue - vecteur avec les poids pour une main.

Exemple

> 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

Version de code lisible par l'homme:

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

Axiome, 292 octets

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

Une application de force brute. Cela minimiserait l'ensemble

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

parce que si c'est minimum

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

ce serait aussi un minimum

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

où (réduire (+, a) -réduire (+, r)) et réduire (+, r) sont les 2 poids de deux sacs (mais cette dernière formule ne me trouve pas le minimum, dans l'application). Ungolf et résultats

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