Алгоритм разделения списка чисел на 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.Предел суммы игроков составляет totalscores/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}
Все поля с цифрами являются возможными решениями для одной сумки.Выберите тот, который находится дальше всего в правом нижнем углу.
КСТАТИ:Это называется задача о рюкзаке.
Если все веса (W1, ..., WN и W) являются неотрицательными целыми числами, проблема рюкзака может быть решена в псевдополиномиальное время с использованием динамического программирования.
Что ж, вы можете найти решение с процентной точностью за полиномиальное время, но чтобы на самом деле найти оптимальное (абсолютно минимальную разность) решение, проблема является NP-полной.Это означает, что задача не имеет решения за полиномиальное время.В результате даже при относительно небольшом списке чисел решение требует слишком больших вычислительных ресурсов.Если вам действительно нужно решение, взгляните на некоторые алгоритмы аппроксимации для этого.
К.Учитывая мультимножество S целых чисел, есть ли способ разделить 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)
На самом деле это PARTITION, частный случай KNAPSACK.
Это NP Complete с псевдополиномиальными алгоритмами dp.Псевдо-полиномиал относится к тому факту, что время выполнения зависит от диапазона весов.
В общем, вам придется сначала решить, существует ли точное решение, прежде чем вы сможете принять эвристическое решение.
Тестовый пример, в котором ваш метод не работает:
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 бит!).
Таким образом, для всех тестовых данных и неуклюжих крайних случаев, которые я собрал во время тестирования своих первых двух попыток, он дает один и тот же ответ.По крайней мере, для тех, которые я проверял с помощью комбинаторного решателя, я знать они правы.Но я все еще проваливаю заявку из-за неправильного ответа!
Я не прошу кого-либо исправить здесь мой код, но я был бы очень рад, если бы кто-нибудь смог найти случай, для которого приведенный ниже код генерирует неправильный ответ.
Спасибо,
Грэм
PS Этот код всегда выполняется в течение установленного срока, но это далеко из оптимизированного.я делаю это простым, пока оно не пройдет тест, а затем у меня есть несколько идей, как его ускорить, может быть, в 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
Для повышения производительности вы экономите вычисления, заменяя add() и 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, последний), t2<-que(2nd, последний-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 для любой заданной суммы, но не сообщает вам содержимое ни одного из разделов.
