Алгоритм для Деления списка чисел в 2 равных списка суммы

Ну, вы можете найти решение с процентной точностью за полиномиальное время, но для того, чтобы найти оптимальное (абсолютное минимальное различие) решение, задача является NP-полной. Это означает, что нет решения проблемы за полиномиальное время. В результате, даже при относительно небольшом списке чисел, он слишком трудоемок для решения. Если вам действительно нужно решение, взгляните на некоторые алгоритмы аппроксимации для этого.

http://en.wikipedia.org/wiki/Subset_sum_problem

Вы можете немного затянуть петлю, используя следующее:

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

Для повышения производительности вы экономите вычисления, заменяя append () и sum () промежуточными итогами.

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

Динамическое программирование - это решение, которое вы ищете.

Пример с [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: Это называется задача о рюкзаке .

Если все веса (w1, ..., wn и W) равны неотрицательные целые числа, рюкзак проблема может быть решена в псевдополиномиальное время с использованием динамического программирование.

Обратите внимание, что это тоже эвристика, и я вынес сортировку из функции.

 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)

В. Для мультимножества S целых чисел существует ли способ разделить S на два подмножества S1 и S2 так, чтобы сумма чисел в S1 была равна сумме чисел в S2?

A. Задача о разделении .

Удачи приблизительно. :)

После некоторого размышления, для не слишком большой проблемы, я думаю, что лучший вид эвристики будет примерно таким:

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, если проблема больше.

Это решает все проблемы. упоминается выше почти всегда.

Поскольку списки должны быть равны, проблема вовсе не в 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"

Edit : Я полагаю, что это тоже неправильный метод. Неправильные результаты!

Это фактически РАЗДЕЛ, частный случай 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

В предыдущем комментарии я предположил, что проблема в том виде, в каком она была установлена, решаема, поскольку тщательно отобрали тестовые данные, чтобы они были совместимы с различными алгоритмами в отведенное время. Оказалось, что это не так - это проблема ограничений - числа не выше 450 и окончательный набор не более 50 чисел является ключевым. Они совместимы с решением проблемы с использованием решения динамического программирования, которое я разместил в более позднем посте. Ни один из других алгоритмов (эвристика или исчерпывающее перечисление с помощью комбинаторного генератора шаблонов), возможно, не может работать, потому что будут тестовые примеры, достаточно большие или достаточно сложные, чтобы сломать эти алгоритмы. Честно говоря, это довольно неприятно, потому что другие решения более сложные и, безусловно, более увлекательные. Обратите внимание, что без большой дополнительной работы решение динамического программирования просто говорит, возможно ли решение с N / 2 для любой заданной суммы, но не сообщает вам содержимое любого раздела.

Очевидно, они ищут ранцевое решение для динамического программирования. Итак, после моей первой попытки (я подумал, что это довольно хорошая исходная эвристика) и моей второй попытки (действительно хитрое точное комбинаторное решение, которое работало для небольших наборов данных и даже для наборов до 100 элементов, длина которых равна числу уникальные значения были низкими), я, наконец, уступил давлению сверстников и написал то, что они хотели (не слишком сложно - обработка дублированных записей была самой сложной частью - базовый алгоритм, на котором я его основал, работает только в том случае, если все входные данные уникальны - Я уверен, что long long достаточно велик, чтобы вместить 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;
}