Был теплый летний вечер ...

когда моя глупая машина решила сломаться посреди дороги по дороге обратно из супермаркета. Я отодвинул его в сторону и решил идти домой. Я открыл сундук, чтобы достать продуктовый магазин и оставшиеся вещи. Тогда я заметил, что предметы не были равномерно упакованы. В некоторых сумках были более тяжелые вещи, в то время как в других было мало более легких вещей - в некоторых даже было несколько таких вещей. Чтобы мне было легче переносить, я решил сгруппировать все в две сумки и сделать их веса как можно ближе друг к другу.

Твоя цель

состоит в том, чтобы помочь мне переставить предметы в две хозяйственные сумки таким образом, чтобы разница между обеими сумками была близка к нулю, насколько это возможно.
Математически:

ВЕС _{ЛЕВАЯ РУКА} - ВЕС _{ВПРАВО РУКА} ≈ 0

пример

Если у меня было только 2 предмета - хлеб и арахисовое масло, а вес хлеба - 250 грамм, а арахисового масла - 150 грамм, то лучше всего переносить их отдельно двумя руками.

W _LH - W _RH = W _(ХЛЕБ) - W _(P.BUTTER)
250 - 150 = 100

Другая возможность:

W _{(ХЛЕБ, P.BUTTER)} - W _{(пустая рука)} = (250 + 150) - 0 = 400

Это не лучше, чем в нашем первом случае, поэтому вы должны пойти с первым.

Ваш код должен

1. введите числа, указывающие на вес предметов в корзине. Единицы измерения не важны, но они должны быть одинаковыми (в идеале килограммы или граммы). Ввод может быть сделан один за другим или все сразу. Вы можете ограничить общее количество до 20 пунктов, если хотите.
2. Формат ввода / тип зависит от вас, но ничего другого не должно быть, кроме весов.
3. Разрешен любой язык, но придерживайтесь стандартных библиотек.
4. Вывод на дисплей. Опять же, вы можете выбрать формат, но объясните формат в своем посте. то есть, как мы можем сказать, какие из них являются левосторонними, а какие - правосторонними.

Точки

1. Самый короткий код выигрывает.

намек

Два возможных алгоритма, о которых я мог подумать, - это дифференцирование (быстрее) и перестановки / комбинации (медленнее). Вы можете использовать эти или любые другие алгоритмы, которые делают эту работу.

Pyth, 9 байт

ehc2osNyQ

Форматы ввода, вывода:

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

Демонстрация.

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.

Это работает, потому что yвозвращает подмножества в таком порядке, что каждое подмножество и его дополнение равноудалены от центра. Поскольку сумма подмножества и сумма его дополнения всегда будут равноудалены от центра, список после osNyQтакже будет иметь это свойство. Таким образом, центр двух элементов osNyQявляется дополнением и должен иметь оптимальное разбиение. Мы извлекаем первый из этих двух элементов и печатаем его.

Pyth, 16

ho.a-FsMNs./M.pQ

Это принимает входные данные как питонический список на STDIN. В результате получается список из 2 списков, первый из которых представляет собой товары в одной сумке, а второй список представляет товары во второй сумке. Этот перебор форсирует все комбинации, поэтому он будет работать очень медленно (или не хватит памяти) для больших входов.

Попробуйте это онлайн здесь

Для поддержки обработки только одного ввода это доходит до 17:

hho.a-FsMNs./M.pQ

Это напечатает значения, которые идут в одну руку.

CJam, 19 18 байтов

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

Это анонимная функция, которая извлекает массив целых чисел из стека и возвращает массив целых чисел, разделенных пробелом.

Спасибо @ jimmy23013 за его оригинальный :*трюк, который сэкономил 1 байт.

Попробуйте онлайн в интерпретаторе CJam .

Как это работает

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.

Обозначим общий вес сумок с W . Затем, если мешки в одной руке весят W / 2 - D / 2 , то мешки в другой руке должны весить и W - (W / 2 - D / 2) = W / 2 + D / 2 .

Мы пытаемся свести к минимуму разность D . Но (W / 2 - D / 2) (W / 2 + D / 2) = W ^ 2/4 - D ^ 2/4 , которая становится больше, когда D становится меньше.

Таким образом, максимальное произведение соответствует минимальной разности.

Python 2.7, 161 , 160

код

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

Алгоритм

2 х W _{одной рукой} = общий вес
W _{одной рукой} ~ общий вес / 2

Проверьте, приближается ли каждая комбинация к половине общего веса. Итерируйте и найдите лучший.

вход

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

выход

(2, 3)

Отображаемый кортеж идет в одну руку, а те, которые не отображаются, идут в другую (это не противоречит правилам).

JavaScript ( ES6 ) 117

Использование битовой маски для пробования каждого возможного разбиения, поэтому оно ограничено 31 элементом (хорошо с правилами). Как и ответ на вопрос, он выводит только одну руку. Примечание: я ищу минимальную разницу> = 0, чтобы избежать Math.abs, так как для каждого min <0 есть еще> 0, просто меняются руки.

Чтобы проверить: запустите фрагмент в Firefox, введите список чисел через запятую или через пробел.

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 байта

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

Выводит список предметов в одну руку. Недостающие элементы переходят в другую руку.

Использование: f [7,7,7,10,11]->[7,7,7]

Для всех подпоследовательностей sвходного списка lвычисляют абсолютное значение разницы в весе между sнедостающими элементами l. Найдите минимум.

Haskell, 51 байт

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

Выходной формат таков, что левые веса являются положительными, а правые - отрицательными.

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

Чтобы сгенерировать каждое возможное разбиение, мы используем mapM(\x->[x,-x])lдля отрицания все возможные подмножества элементов. Затем ((,)=<<abs.sum)пометьте каждый абсолютной суммой и snd$minimum$((,)=<<abs.sum)возьмите элемент с наименьшей меткой.

Я не мог получить это бессмысленно из-за проблем с проверкой типов.

R (234)

дольше и медленнее решение с R.

Функция:

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

Ожидаемый ввод - вектор с весами.
Ожидаемый результат - вектор с весами на одну руку.

пример

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

Аксиома, 292 байта

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={abs(reduce(+,a)quo 2-reduce(+,x))|x in powerSet(a)}

потому что если это минимум

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

это тоже будет минимум

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

где (уменьшите (+, a) -reduce (+, r)) и уменьшите (+, r) 2 веса двух сумок (но эта последняя формула не находит для меня минимума в приложении). Унгольф и результаты

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