разделить список на две части, чтобы их сумма была ближе всего друг к другу - PullRequest
Новая
       16

разделить список на две части, чтобы их сумма была ближе всего друг к другу

8 голосов
/ 18 декабря 2010

Это проблема hard алгоритмов, которая:

Разделит список на 2 части (сумма), чтобы их сумма была ближе всего (больше) друг к другу

длина спискаравно 1 <= n <= 100, а их (числовые) веса 1 <= w <= 250 приведены в вопросе. </p>

Например: 23 65 134 32 95 123 34

1.сумма = 256

2.сум = 250

1.list = 1 2 3 7

2.list = 4 5 6

У меня естьалгоритм, но он не работал для всех входов.

  1. init.списки list1 = [], list2 = []
  2. Сортировка элементов (заданный список) [23 32 34 65 95 123 134]
  3. всплывающее последнее (максимальное значение)
  4. вставить в список, который отличается меньше

Реализация: list1 = [], list2 = []

  1. выбрать 134 вставить список1.list1 = [134]
  2. выберите 123 вставить список2.потому что если вы добавите в список1, разница станет больше3. выберите 95 и вставьте список2.потому что сумма (список2) + 95 - сумма (список1) меньше.

и так далее ...

Ответы [ 3 ]

7 голосов
/ 18 декабря 2010

Вы можете переформулировать это как проблема ранца .

У вас есть список предметов с общим весом M, который должен быть помещен в корзину, которая может выдержать максимальный вес M / 2. Товары, упакованные в мусорное ведро, должны весить как можно больше, но не больше, чем вмещает мусорное ведро.

Для случая, когда все веса неотрицательны, эта задача является только слабо NP-полной и имеет решения за полиномиальное время.

Описание решений динамического программирования для этой проблемы можно найти в Wikipedia .

4 голосов
/ 18 декабря 2010

Проблема в NPC, но есть псевдополиномиальный алгоритм для нее, это 2-секционная проблема, вы можете следовать пути псевдополиномиального алгоритма времени для сумма подмножества проблема, чтобы решить это.Если входной размер полиномиально связан с входными значениями, то это можно сделать за полиномиальное время.

В вашем случае (вес <250) это полином (потому что вес <= 250 n => суммы <= 250 n ^ 2). </p>

Пусть Sum = сумма весов, мы должнысоздать двумерный массив A, затем построить A, Столбец по столбцу

A [i, j] = true, если (j == weight [i] или j - weight [i] = weight [k] (k)находится в списке)).

Создание массива с помощью этого алгоритма занимает O (n ^ 2 * sum / 2).

Наконец мы должны найти наиболее ценный столбец, который имеет истинное значение.

Вот пример:

пунктов: {0,1,2,3} весов: {4,7,2,8} => сумма = 21 сумма / 2 = 10 

items/weights 0|  1  | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10    
  --------------------------------------------------------- 
  |0             |  0  | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0
  |1             |  0  | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0
  |2             |  0  | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1
  |3             |  0  | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1

Так как [10, 2] == true раздел равен 10, 11

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

bool partition( vector< int > C ) {
 // compute the total sum
 int n = C.size();
 int N = 0;
 for( int i = 0; i < n; i++ ) N += C[i];
 // initialize the table 
 T[0] = true;
 for( int i = 1; i <= N; i++ ) T[i] = false;
 // process the numbers one by one
 for( int i = 0; i < n; i++ )
  for( int j = N - C[i]; j >= 0; j--)
   if( T[j] ) T[j + C[i]] = true;

 for(int i = N/2;i>=0;i--)
    if (T[i])
      return i;
 return 0;
}

Я только что возвратил первое T [i], которое является истинным, вместо того, чтобы возвращать T [N / 2] (от макс до мин).

Поиск путичто дает это значение не сложно.

2 голосов
/ 18 декабря 2010

Эта проблема, по крайней мере, так же сложна, как и проблема с полной NP сумма подмножества . Ваш алгоритм жадный алгоритм. Этот тип алгоритма быстр и может быстро генерировать приближенное решение, но не может найти точное решение NP-полной задачи.

Подход с применением грубой силы, вероятно, является самым простым способом решения вашей проблемы, хотя он будет медленным, если будет слишком много элементов.

  • Попробуйте все возможные способы разбиения элементов на два набора и рассчитайте абсолютную разницу в суммах.
  • Выберите раздел, для которого абсолютная разница минимальна.

Генерация всех разделов может быть выполнена с учетом двоичного представления каждого целого числа от 0 до 2 ^ n, где каждая двоичная цифра определяет, находится ли соответствующий элемент в левом или правом разделе.

...