숫자 목록을 2 개의 동일한 합계 목록으로 나누는 알고리즘
https://stackoverflow.com/questions/890171
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
숫자 목록이 있습니다.
이 목록은 합계가 최소화 된 2 개의 동일한 크기 목록으로 나뉩니다. 합계를 인쇄해야합니다.
#Example:
>>>que = [2,3,10,5,8,9,7,3,5,2]
>>>make_teams(que)
27 27
어떤 경우에는 다음 코드 알고리즘에 오류가 있습니까?
이것을 최적화 및/또는 파이썬화하려면 어떻게합니까?
def make_teams(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
val = (que.pop(), que.pop())
if sum(t1)>sum(t2):
t2.append(val[0])
t1.append(val[1])
else:
t1.append(val[0])
t2.append(val[1])
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
해결책
새로운 솔루션
이것은 휴리스틱 컬링을 사용한 폭이 큰 검색입니다. 나무는 플레이어 깊이/2로 제한됩니다. 플레이어 합액 제한은 총체/2입니다. 플레이어 풀이 100 인 경우 해결하는 데 약 10 초가 걸렸습니다.
def team(t):
iterations = range(2, len(t)/2+1)
totalscore = sum(t)
halftotalscore = totalscore/2.0
oldmoves = {}
for p in t:
people_left = t[:]
people_left.remove(p)
oldmoves[p] = people_left
if iterations == []:
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
for n in iterations:
newmoves = {}
for total, roster in oldmoves.iteritems():
for p in roster:
people_left = roster[:]
people_left.remove(p)
newtotal = total+p
if newtotal > halftotalscore: continue
newmoves[newtotal] = people_left
oldmoves = newmoves
solution = min(map(lambda i: (abs(float(i)-halftotalscore), i), oldmoves.keys()))
return (solution[1], sum(oldmoves[solution[1]]), oldmoves[solution[1]])
print team([90,200,100])
print team([2,3,10,5,8,9,7,3,5,2])
print team([1,1,1,1,1,1,1,1,1,9])
print team([87,100,28,67,68,41,67,1])
print team([1, 1, 50, 50, 50, 1000])
#output
#(200, 190, [90, 100])
#(27, 27, [3, 9, 7, 3, 5])
#(5, 13, [1, 1, 1, 1, 9])
#(229, 230, [28, 67, 68, 67])
#(150, 1002, [1, 1, 1000])
또한 GS의 설명을 사용하여 이것을 해결하려고 시도했지만, 실행중인 총계를 저장하여 충분한 정보를 얻는 것은 불가능합니다. 그리고 당신이 저장 한 경우 둘 다 항목의 수와 총계는 불필요한 데이터를 보관 한 것을 제외 하고이 솔루션과 동일합니다. N-1 및 N 반복을 Numplayers/2까지 유지하면됩니다.
나는 이항 계수를 기반으로 한 오래된 철저한 것을 가졌습니다 (역사를 보면). 그것은 길이 10의 예제 문제를 해결했지만, 나는 경쟁이 최대 100의 사람들을 가졌다는 것을 알았습니다.
다른 팁
동적 프로그래밍 당신이 찾고있는 솔루션입니다.
4, 3, 10, 3, 2, 5]의 예 : :
X-Axis: Reachable sum of group. max = sum(all numbers) / 2 (rounded up)
Y-Axis: Count elements in group. max = count numbers / 2 (rounded up)
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 | | | | 4| | | | | | | | | | | // 4
2 | | | | | | | | | | | | | | |
3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | | | | | | | // 3 2 | | | | | | | 3| | | | | | | | 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 10 2 | | | | | | | 3| | | | | |10|10| 3 | | | | | | | | | | | | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | | 3| 4| | | | | |10| | | | | // 3 2 | | | | | | 3| 3| | | | | |10|10| 3 | | | | | | | | | | 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 | | 2| 3| 4| | | | | |10| | | | | // 2 2 | | | | | 2| 3| 3| | | | | 2|10|10| 3 | | | | | | | | 2| 2| 3| | | | |
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 | | 2| 3| 4| 5| | | | |10| | | | | // 5
2 | | | | | 2| 3| 3| 5| 5| | | 2|10|10|
3 | | | | | | | | 2| 2| 3| 5| 5| | |
^
12는 우리의 행운의 숫자입니다! 그룹을 얻기위한 역 추적 :
12 - 5 = 7 {5}
7 - 3 = 4 {5, 3}
4 - 4 = 0 {5, 3, 4}
그런 다음 다른 세트를 계산할 수 있습니다. {4,3,10,3,2,5} - {5,3,4} = {10,3,2}
숫자가있는 모든 필드는 하나의 백에 대한 솔루션입니다. 오른쪽 하단에서 가장 먼 곳을 선택하십시오.
BTW : 이거라고합니다 Knapsack-problem.
모든 가중치 (w1, ..., wn 및 w)가 음이 아닌 정수 인 경우, 동적 프로그래밍을 사용하여 의사-폴리 동맥 시간으로 배낭 문제를 해결할 수 있습니다.
글쎄, 당신은 다항식 시간의 정밀도에 대한 솔루션을 찾을 수 있지만 실제로 최적의 (절대 최소 차이) 솔루션을 찾으려면 문제가 NP- 완성됩니다. 이것은 문제에 대한 다항식 시간 솔루션이 없음을 의미합니다. 결과적으로, 비교적 작은 숫자 목록을 사용하더라도 해결하기에는 너무 집중적입니다. 솔루션이 실제로 필요한 경우 이에 대한 근사 알고리즘 중 일부를 살펴보십시오.
Q. 주어진 a 정수의 멀티 세트, S를 분할하는 방법이 있습니까? 두 개의 서브 세트 S1 및 S2 합계 S1의 숫자 중 S2의 숫자 합계와 같습니까?
행운을 빕니다. :)
그것은 또한 휴리스틱이고 나는 종류를 함수에서 옮겼습니다.
def g(data):
sums = [0, 0]
for pair in zip(data[::2], data[1::2]):
item1, item2 = sorted(pair)
sums = sorted([sums[0] + item2, sums[1] + item1])
print sums
data = sorted([2,3,10,5,8,9,7,3,5,2])
g(data)
실제로는 분할, 특별한 배낭입니다.
의사-폴리 언 DP 알고리즘으로 NP가 완료됩니다. 의사 폴리 언어의 의사는 실행 시간이 가중치의 범위에 의존한다는 사실을 말합니다.
일반적으로 휴리스틱 솔루션을 인정하기 전에 정확한 솔루션이 있는지 먼저 결정해야합니다.
방법이 작동하지 않는 테스트 케이스입니다
que = [1, 1, 50, 50, 50, 1000]
문제는 쌍으로 물건을 분석하고 있으며이 예에서는 50 대 모두가 같은 그룹에 있기를 원합니다. 쌍 분석 측면을 제거하고 한 번에 한 항목 만 수행하면 해결해야합니다.
다음은이를 수행하는 코드입니다
def make_teams(que):
que.sort()
que.reverse()
if len(que)%2: que.insert(0,0)
t1,t2 = [],[]
while que:
if abs(len(t1)-len(t2))>=len(que):
[t1, t2][len(t1)>len(t2)].append(que.pop(0))
else:
[t1, t2][sum(t1)>sum(t2)].append(que.pop(0))
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2)), "\n"
if __name__=="__main__":
que = [2,3,10,5,8,9,7,3,5,2]
make_teams(que)
que = [1, 1, 50, 50, 50, 1000]
make_teams(que)
이것은 27, 27 및 150, 1002에게 나에게 의미가있는 답입니다.
편집하다: 검토에서, 나는 이것이 실제로 작동하지 않는다고 생각하지만 결국 그 이유는 확실하지 않습니다. 유용 할 수 있으므로 테스트 코드를 여기에 게시하겠습니다. 테스트는 동일한 합이있는 임의의 순서를 생성하고, 이들을 합치고 (슬픈 결과와 함께) 비교합니다.
#2 편집 : 미지의 것으로 지적 된 예를 바탕으로 [87,100,28,67,68,41,67,1], 내 방법이 작동하지 않는 이유는 분명합니다. 구체적으로,이 예를 해결하기 위해, 두 개의 가장 큰 숫자는 유효한 솔루션을 얻기 위해 동일한 시퀀스에 추가되어야합니다.
def make_sequence():
"""return the sums and the sequence that's devided to make this sum"""
while 1:
seq_len = randint(5, 200)
seq_max = [5, 10, 100, 1000, 1000000][randint(0,4)]
seqs = [[], []]
for i in range(seq_len):
for j in (0, 1):
seqs[j].append(randint(1, seq_max))
diff = sum(seqs[0])-sum(seqs[1])
if abs(diff)>=seq_max:
continue
if diff<0:
seqs[0][-1] += -diff
else:
seqs[1][-1] += diff
return sum(seqs[0]), sum(seqs[1]), seqs[0], seqs[1]
if __name__=="__main__":
for i in range(10):
s0, s1, seq0, seq1 = make_sequence()
t0, t1 = make_teams(seq0+seq1)
print s0, s1, t0, t1
if s0 != t0 or s1 != t1:
print "FAILURE", s0, s1, t0, t1
그들은 분명히 동적 프로그래밍 배낭 솔루션을 찾고 있습니다. 그래서 첫 번째 노력 (내가 생각한 꽤 좋은 오리지널 휴리스틱)과 두 번째 노력 (짧은 데이터 세트에서 작동하는 정말 비열한 정확한 조합 솔루션, 심지어 최대 100 개의 요소까지의 세트에 대해서 독특한 값은 낮았고 마침내 동료 압력에 굴복하고 그들이 원하는 것을 썼습니다 (너무 어려운 것은 아닙니다 - 복제 된 항목을 가장 까다로운 부분이었습니다. 모든 입력이 독특한 경우에만 작동하는 기본 알고리즘입니다. 확실합니다. 기뻐요 긴 50 비트를 유지하기에 충분히 큽니다!).
따라서 모든 테스트 데이터와 어색한 모서리 케이스에 대해 처음 두 가지 노력을 테스트하면서 함께 모이려면 동일한 답변을 제공합니다. 적어도 조합 솔버로 확인한 것들에 대해서는 알다 맞습니다. 그러나 나는 여전히 약간의 정답으로 제출에 실패하고 있습니다!
나는 여기에서 내 코드를 수정 해달라고 요청하지는 않지만 아래 코드가 잘못된 답을 생성하는 사례를 찾을 수 있다면 매우 큰 일입니다.
감사,
그레이엄
추신이 코드는 항상 시간 제한 내에 실행되지만 멀리 최적화에서. 테스트를 통과 할 때까지 간단하게 유지 한 다음 10 배 이상 속도를 높이기위한 아이디어가 있습니다.
#include <stdio.h>
#define TRUE (0==0)
#define FALSE (0!=0)
static int debug = TRUE;
//int simple(const void *a, const void *b) {
// return *(int *)a - *(int *)b;
//}
int main(int argc, char **argv) {
int p[101];
char *s, line[128];
long long mask, c0[45001], c1[45001];
int skill, players, target, i, j, tests, total = 0;
debug = (argc == 2 && argv[1][0] == '-' && argv[1][1] == 'd' && argv[1][2] == '\0');
s = fgets(line, 127, stdin);
tests = atoi(s);
while (tests --> 0) {
for (i = 0; i < 45001; i++) {c0[i] = 0LL;}
s = fgets(line, 127, stdin); /* blank line */
s = fgets(line, 127, stdin); /* no of players */
players = atoi(s);
for (i = 0; i < players; i++) {s = fgets(line, 127, stdin); p[i] = atoi(s);}
if (players == 1) {
printf("0 %d\n", p[0]);
} else {
if (players&1) p[players++] = 0; // odd player fixed by adding a single player of 0 strength
//qsort(p, players, sizeof(int), simple);
total = 0; for ( i = 0; i < players; i++) total += p[i];
target = total/2; // ok if total was odd and result rounded down - teams of n, n+1
mask = 1LL << (((long long)players/2LL)-1LL);
for (i = 0; i < players; i++) {
for (j = 0; j <= target; j++) {c1[j] = 0LL;} // memset would be faster
skill = p[i];
//add this player to every other player and every partial subset
for (j = 0; j <= target-skill; j++) {
if (c0[j]) c1[j+skill] = c0[j]<<1; // highest = highest j+skill for later optimising
}
c0[skill] |= 1; // so we don't add a skill number to itself unless it occurs more than once
for (j = 0; j <= target; j++) {c0[j] |= c1[j];}
if (c0[target]&mask) break; // early return for perfect fit!
}
for (i = target; i > 0; i--) {
if (debug || (c0[i] & mask)) {
fprintf(stdout, "%d %d\n", i, total-i);
if (debug) {
if (c0[i] & mask) printf("******** ["); else
printf(" [");
for (j = 0; j <= players; j++) if (c0[i] & (1LL<<(long long)j)) printf(" %d", j+1);
printf(" ]\n");
} else break;
}
}
}
if (tests) printf("\n");
}
return 0;
}
class Team(object):
def __init__(self):
self.members = []
self.total = 0
def add(self, m):
self.members.append(m)
self.total += m
def __cmp__(self, other):
return cmp(self.total, other.total)
def make_teams(ns):
ns.sort(reverse = True)
t1, t2 = Team(), Team()
for n in ns:
t = t1 if t1 < t2 else t2
t.add(n)
return t1, t2
if __name__ == "__main__":
import sys
t1, t2 = make_teams([int(s) for s in sys.argv[1:]])
print t1.members, sum(t1.members)
print t2.members, sum(t2.members)
>python two_piles.py 1 50 50 100
[50, 50] 100
[100, 1] 101
성능을 위해서는 부록 () 및 sum ()을 총을 실행중인 것으로 바꾸어 계산을 저장합니다.
다음을 사용하여 루프를 약간 조일 수 있습니다.
def make_teams(que):
que.sort()
t1, t2 = []
while que:
t1.append(que.pop())
if sum(t1) > sum(t2):
t2, t1 = t1, t2
print min(sum(t1),sum(t2)), max(sum(t1),sum(t2))
목록은 나와 동일해야하므로 문제는 전혀 NP가 아닙니다.
정렬 된 목록을 패턴 T1 <-que (1st, last), t2 <-que (2nd, last-1)로 나눕니다.
def make_teams2(que):
que.sort()
if len(que)%2: que.insert(0,0)
t1 = []
t2 = []
while que:
if len(que) > 2:
t1.append(que.pop(0))
t1.append(que.pop())
t2.append(que.pop(0))
t2.append(que.pop())
else:
t1.append(que.pop(0))
t2.append(que.pop())
print sum(t1), sum(t2), "\n"
편집하다: 나는 이것이 잘못된 방법이라고 생각합니다. 잘못된 결과!
너무 큰 문제에 대해 어떤 생각을 한 후에, 나는 최고의 휴리스틱이 다음과 같은 것일 것이라고 생각합니다.
import random
def f(data, nb_iter=20):
diff = None
sums = (None, None)
for _ in xrange(nb_iter):
random.shuffle(data)
mid = len(data)/2
sum1 = sum(data[:mid])
sum2 = sum(data[mid:])
if diff is None or abs(sum1 - sum2) < diff:
sums = (sum1, sum2)
print sums
문제가 더 크면 nb_iter를 조정할 수 있습니다.
위에서 언급 한 모든 문제를 대부분 항상 해결합니다.
이전의 의견에서 나는 세트로서의 문제가 할당 된 시간 내에 다양한 알고리즘과 호환되도록 테스트 데이터를 신중하게 선택했기 때문에 트랙 가능하다는 가설을 세웠다. 이것은 사실이 아닌 것으로 판명되었습니다. 대신 문제 제약 조건입니다. 450 이하의 숫자와 최종 세트가 50 이하의 숫자가 핵심입니다. 이들은 나중에 게시물에 넣은 동적 프로그래밍 솔루션을 사용하여 문제를 해결하는 것과 호환됩니다. 다른 알고리즘 (휴리스틱 또는 조합 패턴 생성기에 의한 철저한 열거) 중 어느 것도 이러한 알고리즘을 파괴하기에 충분히 큰 테스트 케이스가 있기 때문에 작동 할 수 없습니다. 다른 솔루션이 더 도전적이고 확실히 더 재미 있기 때문에 정직한 것은 성가신 일입니다. 추가 작업이 많지 않으면 동적 프로그래밍 솔루션에 따르면 주어진 금액에 대해 N/2로 솔루션이 가능한지 여부를 말하지만 두 파티션의 내용을 알려주는 것은 아닙니다.
