따뜻한 여름 저녁이었습니다 …
내 어리석은 차가 슈퍼마켓에서 돌아 오는 길의 한가운데서 고장 났을 때 나는 그것을 부업으로 밀고 집으로 걸어 가기로 결정했다. 나는 식료품과 남은 물건을 꺼내기 위해 트렁크를 열었습니다. 그때 물품이 고르게 포장되지 않았다는 것을 알게되었습니다. 일부 가방에는 더 무거운 물건이 있었지만 다른 가방에는 가벼운 물건이 거의 없었습니다. 휴대하기 쉽도록 모든 것을 두 개의 가방에 그룹화하고 무게를 가능한 한 가깝게 만들기로 결정했습니다.
네 목표
두 백의 차이가 최대한 0에 가까워 지도록 두 개의 쇼핑백에 상품을 다시 정렬하는 데 도움이됩니다.
수학적으로 :
체중 왼쪽 손 — 체중 오른쪽 손 ≈ 0
예
빵과 땅콩 버터 2 개만 가지고 빵의 무게가 250 그램이고 땅콩 버터가 150 그램 인 경우 가장 좋은 방법은 두 손으로 따로 운반하는 것입니다.
W LH -W RH = W (빵) -W (버터) 250-150
= 100
다른 가능성은 다음과 같습니다.
W (빵, 버터) -W (빈 손) = (250 + 150)-0 = 400
이것은 우리의 첫 번째 경우보다 낫지 않으므로 첫 번째 경우와 함께 가야합니다.
코드는
- 쇼핑백에있는 품목의 무게를 나타내는 숫자를 입력하십시오. 단위는 중요하지 않지만 동일해야합니다 (이상적으로 킬로그램 또는 그램). 입력은 한 번에 하나씩 또는 모두 수행 할 수 있습니다. 원하는 경우 총 개수를 최대 20 개 항목으로 제한 할 수 있습니다.
- 입력 형식 / 유형은 사용자가 선택해야하지만 가중치 이외의 다른 것은 없어야합니다.
- 모든 언어가 허용되지만 표준 라이브러리를 고수하십시오.
- 출력을 표시합니다. 다시 한 번, 형식을 자유롭게 선택할 수 있지만 게시물에서 형식을 설명하십시오. 즉, 왼손잡이 항목과 오른 손잡이 항목을 구분할 수있는 방법은 무엇입니까?
전철기
- 가장 짧은 코드가 승리합니다.
힌트
내가 생각할 수있는 두 가지 가능한 알고리즘은 미분 (빠른)과 순열 / 조합 (느린)입니다. 작업을 수행하는 이들 또는 다른 알고리즘을 사용할 수 있습니다.
답변
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
는 보수이며 최적의 분할을 가져야합니다. 이 두 요소 중 첫 번째 요소를 추출하여 인쇄합니다.
답변
피스, 16
ho.a-FsMNs./M.pQ
이것은 입력을 STDIN의 pythonic list로 가져옵니다. 출력은 두 개의 목록으로 구성되며 첫 번째 목록은 한 백에있는 항목이고 두 번째 목록은 두 번째 백에있는 항목을 나타냅니다. 이 무차별 동작은 모든 조합을 강제하므로 큰 입력의 경우 매우 느리게 (또는 메모리 부족) 실행됩니다.
하나의 입력 만 처리 할 수 있도록 최대 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 가 작아 질 수록 커 집니다.
따라서 최대 곱은 최소 차이에 해당합니다.
답변
파이썬 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 x W 한 손 = 총 무게
W 한 손 ~ 총 무게 / 2
각 조합이 총 중량의 절반에 가까워지고 있는지 확인하십시오. 반복하고 가장 좋은 것을 찾으십시오.
입력
>>>[1,2,3,4]
산출
(2, 3)
표시된 튜플은 한 손에 들어가고 표시되지 않은 튜플은 다른 손에갑니다 (규칙에 위배되지 않음).
답변
자바 스크립트 ( ES6 ) 117
비트 마스크를 사용하여 가능한 모든 분할을 시도하므로 31 개 항목으로 제한됩니다 (규칙에 따름). 심판 답변처럼 한 손만 출력합니다. 참고 : Math.abs를 피하기 위해 최소 차이> = 0을 찾으십시오. 각 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>
답변
하스켈, 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
답변
하스켈, 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)
로 레이블을 지정하고 가장 작은 레이블이 지정된 요소를 사용하십시오.
유형 검사 문제로 인해 포인트를 얻지 못했습니다.