Itu adalah malam musim panas yang hangat ...

ketika mobil bodoh saya memutuskan untuk mogok di tengah jalan dalam perjalanan kembali dari supermarket. Saya mendorongnya ke sampingan dan memutuskan untuk berjalan pulang. Saya membuka bagasi untuk mengambil barang belanjaan dan barang-barang yang tersisa. Saat itulah saya perhatikan barang-barang tidak dikantongi secara merata. Beberapa tas memiliki barang yang lebih berat sementara yang lain memiliki beberapa barang yang lebih ringan - beberapa bahkan memiliki campuran barang-barang tersebut. Agar mudah saya bawa, saya memutuskan untuk mengelompokkan semuanya menjadi dua tas dan membuat bobot mereka sedekat mungkin satu sama lain.

Tujuan Anda

adalah untuk membantu saya mengatur kembali barang-barang menjadi dua tas belanja sedemikian rupa sehingga perbedaan antara kedua tas mendekati nol mungkin.
Secara matematis:

TINGGI _{KIRI TANGAN} - _{TANGAN KANAN} TINGGI. 0

Contoh

Jika saya hanya punya 2 item, Roti dan selai kacang, dan berat roti 250 gram dan selai kacang 150 gram, cara terbaik adalah membawanya secara terpisah dengan dua tangan.

W _LH - W _RH = W _(BREAD) - W _(P.BUTTER)
250 - 150 = 100

Kemungkinan lainnya adalah:

W _{(BREAD, P.BUTTER)} - W _{(tangan kosong)} = (250 + 150) - 0 = 400

Ini tidak lebih baik dari kasus pertama kami, jadi Anda harus memilih yang pertama.

Kode Anda harus

1. mengambil input angka yang menunjukkan bobot item dalam tas belanja. Unit tidak penting, tetapi harus sama (idealnya kilogram atau gram). Input dapat dilakukan satu per satu atau sekaligus. Anda dapat membatasi jumlah total hingga 20 item, jika Anda mau.
2. Format / tipe input terserah Anda untuk memilih, tetapi tidak ada yang lain yang harus ada selain bobot.
3. Bahasa apa pun diperbolehkan, tetapi tetap berpegang pada perpustakaan standar.
4. Output tampilan. Sekali lagi, Anda bebas memilih formatnya, tetapi jelaskan formatnya di posting Anda. yaitu, bagaimana kita bisa tahu mana yang merupakan item tangan kiri dan mana yang merupakan item tangan kanan.

Poin

1. Kode terpendek menang.

Petunjuk

Dua kemungkinan algoritma yang dapat saya pikirkan adalah diferensiasi (lebih cepat) dan permutasi / kombinasi (lebih lambat). Anda dapat menggunakan ini atau algoritma lain yang melakukan pekerjaan.

Pyth, 9 byte

ehc2osNyQ

Input, format keluaran:

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

Demonstrasi.

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.

Ini bekerja karena ymengembalikan himpunan bagian dalam urutan sehingga masing-masing bagian dan pelengkapnya sama dari pusat. Karena jumlah subset dan jumlah komplemennya akan selalu sama dari pusat, daftar setelahnya osNyQjuga akan memiliki properti ini. Dengan demikian, dua elemen tengah osNyQadalah pelengkap, dan harus memiliki pemisahan optimal. Kami mengekstrak yang pertama dari kedua elemen itu dan mencetaknya.

Pyth, 16

ho.a-FsMNs./M.pQ

Ini mengambil input sebagai daftar pythonic pada STDIN. Outputnya adalah daftar 2 daftar dengan daftar pertama adalah item dalam satu tas, dan daftar kedua mewakili item dalam tas kedua. Brute ini memaksa semua kombinasi, sehingga akan berjalan sangat lambat (atau kehabisan memori) untuk input besar.

Cobalah online di sini

Untuk mendukung penanganan hanya satu input, ini naik hingga 17:

hho.a-FsMNs./M.pQ

Ini akan mencetak nilai-nilai yang masuk dalam satu tangan.

CJam, 19 18 byte

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

Ini adalah fungsi anonim yang memunculkan array bilangan bulat dari tumpukan dan mengembalikan array bilangan bulat yang dipisahkan oleh spasi.

Terima kasih kepada @ jimmy23013 untuk :*triknya yang cerdik , yang menghemat 1 byte.

Cobalah online di juru bahasa CJam .

Bagaimana itu bekerja

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.

Menunjukkan berat total tas belanja dengan W . Kemudian, jika tas di salah satu tangan memiliki berat W / 2 - D / 2 , yang di tangan lain harus memiliki berat dan W - (W / 2 - D / 2) = W / 2 + D / 2 .

Kami berusaha untuk meminimalkan perbedaan D . Tetapi (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , yang menjadi lebih besar karena D menjadi lebih kecil.

Dengan demikian, produk maksimal sesuai dengan perbedaan minimal.

Python 2.7, 161 , 160

kode

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

Algoritma

2 x W _{satu tangan} = Berat total
W _{satu tangan} ~ Berat total / 2

Periksa apakah setiap kombinasi semakin mendekati setengah dari total berat. Iterasi dan temukan yang terbaik.

memasukkan

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

keluaran

(2, 3)

Tuple yang ditampilkan berjalan di satu tangan, yang tidak ditampilkan berjalan di tangan yang lain (tidak melanggar aturan).

JavaScript ( ES6 ) 117

Menggunakan bit mask untuk mencoba setiap kemungkinan split, jadi terbatas pada 31 item (ok dengan aturan). Seperti jawaban ref, hasilnya hanya satu tangan. Catatan: saya mencari perbedaan minimum> = 0 untuk menghindari Math.abs, karena untuk setiap menit <0 ada yang lain> 0, hanya bertukar tangan.

Untuk menguji: jalankan snippet di Firefox, masukkan daftar angka koma atau spasi terpisah.

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 byte

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

Menghasilkan daftar item dalam satu tangan. Unsur-unsur yang hilang pergi ke sisi lain.

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

Untuk semua bagian selanjutnya sdari daftar input lhitung nilai absolut dari perbedaan berat antara sdan elemen yang hilang dari l. Temukan minimum.

Haskell, 51 byte

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

Format output adalah bahwa bobot kiri positif dan bobot kanan negatif.

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

Untuk menghasilkan setiap kemungkinan perpecahan, kami menggunakan mapM(\x->[x,-x])l untuk meniadakan setiap subset elemen yang mungkin. Kemudian, beri ((,)=<<abs.sum)label masing-masing dengan jumlah absolut dan snd$minimum$((,)=<<abs.sum)ambil elemen berlabel terkecil.

Saya tidak bisa mendapatkannya secara bebas karena masalah pemeriksaan jenis.

R (234)

solusi yang lebih lama dan lebih lambat dengan R.

Fungsi:

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

Input - vektor yang diharapkan dengan bobot.
Output yang diharapkan - vektor dengan bobot untuk satu tangan.

Contoh

> 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

Versi kode yang dapat dibaca manusia:

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

Aksioma, 292 byte

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

Aplikasi brute force. Ini akan meminimalkan set

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

karena jika minimum

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

itu juga minimum

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

di mana (mengurangi (+, a)-mengurangi (+, r)) dan mengurangi (+, r) adalah 2 berat dua kantung. (Tetapi formula terakhir itu tidak menemukan minimum bagi saya, dalam aplikasi). Ungolf dan hasil

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