따뜻한 여름 저녁이었습니다 …

내 어리석은 차가 슈퍼마켓에서 돌아 오는 길의 한가운데서 고장 났을 때 나는 그것을 부업으로 밀고 집으로 걸어 가기로 결정했다. 나는 식료품과 남은 물건을 꺼내기 위해 트렁크를 열었습니다. 그때 물품이 고르게 포장되지 않았다는 것을 알게되었습니다. 일부 가방에는 더 무거운 물건이 있었지만 다른 가방에는 가벼운 물건이 거의 없었습니다. 휴대하기 쉽도록 모든 것을 두 개의 가방에 그룹화하고 무게를 가능한 한 가깝게 만들기로 결정했습니다.

네 목표

두 백의 차이가 최대한 0에 가까워 지도록 두 개의 쇼핑백에 상품을 다시 정렬하는 데 도움이됩니다.

수학적으로 :

체중 _{왼쪽 손} — 체중 _{오른쪽 손} ≈ 0

예

빵과 땅콩 버터 2 개만 가지고 빵의 무게가 250 그램이고 땅콩 버터가 150 그램 인 경우 가장 좋은 방법은 두 손으로 따로 운반하는 것입니다.

W _LH -W _RH = W _(빵) -W _{(버터) 250-150}

= 100

다른 가능성은 다음과 같습니다.

W _{(빵, 버터)} -W _{(빈 손)} = (250 + 150)-0 = 400

이것은 우리의 첫 번째 경우보다 낫지 않으므로 첫 번째 경우와 함께 가야합니다.

코드는

1. 쇼핑백에있는 품목의 무게를 나타내는 숫자를 입력하십시오. 단위는 중요하지 않지만 동일해야합니다 (이상적으로 킬로그램 또는 그램). 입력은 한 번에 하나씩 또는 모두 수행 할 수 있습니다. 원하는 경우 총 개수를 최대 20 개 항목으로 제한 할 수 있습니다.
2. 입력 형식 / 유형은 사용자가 선택해야하지만 가중치 이외의 다른 것은 없어야합니다.
3. 모든 언어가 허용되지만 표준 라이브러리를 고수하십시오.
4. 출력을 표시합니다. 다시 한 번, 형식을 자유롭게 선택할 수 있지만 게시물에서 형식을 설명하십시오. 즉, 왼손잡이 항목과 오른 손잡이 항목을 구분할 수있는 방법은 무엇입니까?

전철기

1. 가장 짧은 코드가 승리합니다.

힌트

내가 생각할 수있는 두 가지 가능한 알고리즘은 미분 (빠른)과 순열 / 조합 (느린)입니다. 작업을 수행하는 이들 또는 다른 알고리즘을 사용할 수 있습니다.

답변

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.

ho.a-FsMNs./M.pQ

hho.a-FsMNs./M.pQ

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

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.

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

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

(2, 3)

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>

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

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

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