To był ciepły letni wieczór ...

kiedy mój głupi samochód postanowił zepsuć się na środku drogi w drodze powrotnej z supermarketu. Zepchnąłem go na bok i postanowiłem iść do domu. Otworzyłem bagażnik, żeby wyjąć sklep spożywczy i pozostałe rzeczy. Wtedy zauważyłem, że przedmioty nie były równomiernie zapakowane. Niektóre torby miały więcej ciężkich przedmiotów, podczas gdy inne miały kilka lżejszych rzeczy - niektóre miały nawet mieszankę takich przedmiotów. Aby ułatwić mi noszenie, postanowiłem pogrupować wszystko w dwie torby i ustawić ich ciężary jak najbliżej siebie.

Twój cel

jest pomoc w przestawieniu przedmiotów na dwie torby na zakupy w taki sposób, aby różnica między obiema torbami była możliwie bliska zeru.
Matematycznie:

WAGA _{LEWA RĘKA} - WAGA _{PRAWA RĘKA} ≈ 0

Przykład

Gdybym miał tylko 2 przedmioty, Chleb i Masło Orzechowe, a waga Chleba to 250 gramów, a masło orzechowe to 150 gramów, najlepszym sposobem jest noszenie ich osobno w dwóch rękach.

W _LH - W _RH = W _(CHLEB) - W _{(MASŁO) 250-150}
= 100

Inną możliwością jest:

W _{(CHLEB, P. MASŁO)} - W _{(pusta ręka)} = (250 + 150) - 0 = 400

To nie jest lepsze niż nasz pierwszy przypadek, więc powinieneś iść z pierwszym.

Twój kod powinien

1. wprowadź liczby wskazujące wagę przedmiotów w torbie na zakupy. Jednostki nie są ważne, ale powinny być takie same (najlepiej kilogramy lub gramy). Dane wejściowe można wprowadzać pojedynczo lub wszystkie jednocześnie. Jeśli chcesz, możesz ograniczyć całkowitą liczbę do 20 przedmiotów.
2. Format / typ wejściowy zależy od ciebie, ale nic innego nie powinno być obecne poza wagami.
3. Dowolny język jest dozwolony, ale trzymaj się standardowych bibliotek.
4. Wyświetl dane wyjściowe. Ponownie możesz wybrać format, ale wyjaśnij format w swoim poście. tzn. w jaki sposób możemy stwierdzić, które z nich są lewymi, a które prawymi.

Zwrotnica

1. Najkrótszy kod wygrywa.

Wskazówka

Dwa możliwe algorytmy, o których mogłem myśleć, to różnicowanie (szybsze) i permutacje / kombinacje (wolniejsze). Możesz użyć tych lub innych algorytmów, które wykonują zadanie.

Pyth, 9 bajtów

ehc2osNyQ

Formaty wejściowe, wyjściowe:

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

Demonstracja.

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.

Działa to, ponieważ yzwraca podzestawy w takiej kolejności, że każdy podzbiór i jego dopełnienie znajdują się w równej odległości od środka. Ponieważ suma podzbioru i suma jego dopełnienia będzie zawsze jednakowo oddalona od środka, lista po osNyQbędzie również miała tę właściwość. Zatem środkowe dwa elementy osNyQsą dopełnieniami i muszą mieć optymalny podział. Wyodrębniamy pierwszy z tych dwóch elementów i drukujemy go.

Pyth, 16 lat

ho.a-FsMNs./M.pQ

To przyjmuje dane wejściowe jako listę pytonową na STDIN. Dane wyjściowe to lista 2 list, z których pierwsza to pozycje w jednej torbie, a druga lista to pozycje w drugiej torbie. Ten brutalny wymusza wszystkie kombinacje, więc będzie działać bardzo wolno (lub zabraknie pamięci) dla dużych danych wejściowych.

Wypróbuj online tutaj

Aby obsłużyć obsługę tylko jednego wejścia, zwiększa się do 17:

hho.a-FsMNs./M.pQ

Spowoduje to wydrukowanie wartości, które idą jedną ręką.

CJam, 19 18 bajtów

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

Jest to anonimowa funkcja, która wyrzuca tablicę liczb całkowitych ze stosu i zwraca tablicę liczb całkowitych oddzielonych spacją.

Dzięki @ jimmy23013 za jego pomysłową :*sztuczkę, która pozwoliła zaoszczędzić 1 bajt.

Wypróbuj online w interpretatorze CJam .

Jak to działa

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.

Oznaczają całkowity ciężar torby na zakupy z W . Następnie, jeśli worki w jednej ręce ważą W / 2 - D / 2 , te w drugiej ręce muszą ważyć, a W - (W / 2 - D / 2) = W / 2 + D / 2 .

Staramy się zminimalizować różnicę D . Ale (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , który staje się większy, gdy D staje się mniejszy.

Zatem maksymalny produkt odpowiada minimalnej różnicy.

Python 2.7, 161 , 160

kod

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

Algorytm

2 x W na _{jedną rękę} = Całkowita waga
W na _{jedną rękę} ~ Całkowita waga / 2

Sprawdź, czy każda kombinacja zbliża się do połowy całkowitej masy. Iteruj i znajdź najlepszy.

wkład

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

wydajność

(2, 3)

Wyświetlana krotka idzie w jednej ręce, te, które nie są wyświetlane, idą w drugiej (nie jest to niezgodne z regułami).

JavaScript ( ES6 ) 117

Używanie maski bitowej do wypróbowania każdego możliwego podziału, więc jest ograniczona do 31 elementów (ok z zasadami). Podobnie jak odpowiedź ref, wyprowadza tylko jedną rękę. Uwaga: szukam minimalnej różnicy> = 0, aby uniknąć Math.abs, ponieważ dla każdej min <0 jest kolejne> 0, tylko zamiana rąk.

Aby przetestować: uruchom fragment w przeglądarce Firefox, wprowadź listę liczb oddzielonych przecinkami lub spacjami.

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 bajty

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

Wyświetla listę elementów w jednej ręce. Brakujące elementy trafiają do drugiej ręki.

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

Dla wszystkich podsekwencji slisty wejściowej lobliczyć wartość bezwzględną różnicy masy między sbrakującymi elementami a l. Znajdź minimum.

Haskell, 51 bajtów

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

Format wyjściowy jest taki, że odważniki lewe są dodatnie, a odważniki prawe ujemne.

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

Aby wygenerować każdy możliwy podział, używamy mapM(\x->[x,-x])ldo zanegowania każdego możliwego podzbioru elementów. Następnie ((,)=<<abs.sum)oznacz każdą z nich absolutną sumą i snd$minimum$((,)=<<abs.sum)weź najmniejszy element.

Nie mogłem go zdobyć bezcelowo z powodu problemów ze sprawdzaniem typu.

R (234)

dłuższe i wolniejsze rozwiązanie z R.

Funkcjonować:

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

Oczekiwany wkład - wektor z wagami.
Oczekiwany wynik - wektor z wagami na jedną rękę.

Przykład

> 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

Wersja kodu czytelnego dla człowieka:

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

Aksjomat, 292 bajty

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

Brute force. To zminimalizuje zestaw

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

bo jeśli jest minimum

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

to też byłoby minimum

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

gdzie (zmniejsz (+, a) -redukuj (+, r)) i zmniejsz (+, r) to waga dwóch worków. (Ale ta ostatnia formuła nie znalazła dla mnie minimum w aplikacji). Ungolf i wyniki

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