Подмножество в линейном времени

Question

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

1. (20 баллов) Пусть I = {r1, r2, ..., гп} будет множество п произвольных положительных целых чисел и значения в I является отчетливым. I не указан в каком-либо отсортированном порядке. Предположим, что мы хотим, чтобы найти подмножество I ' из я таким образом, что общая сумма всех элементов в я ровно 100 * CEIL (п^0,5) (каждый элемент I может появиться в самых один раз в I '). Представить алгоритм времени O (n) для решения этой проблемы.

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

Итак ... это был трюк?

---

This SO post в основном объясняет, что псевдо-многочлен (линейное) время приближение может быть сделано, если весовые коэффициенты ограничены, но в задаче экзамена веса не ограничены, и в любом случае, учитывая общую сложность экзамена Я был бы потрясен, если бы профессор ожидал, что мы узнаем/придумаем неясный алгоритм динамической оптимизации.

Answer 1

Есть две вещи, которые делают эту проблему возможно:

1. Вход может быть усечен до размера O (SQRT (п)). Нет отрицательных входов, поэтому вы можете отбросить любые цифры, превышающие 100 * sqrt (n), и все входы различны, поэтому мы знаем, что есть не более 100 * sqrt (n) входов, которые имеют значение.
2. Игровое поле имеет размер O (sqrt (n)). Хотя существуют способы O (2^sqrt (n)) объединить входы O (sqrt (n)), которые не имеют значения, вам не нужно заботиться о комбинациях, которые либо оставляют диапазон 100 * sqrt (n), либо избыточно ударяют цель, которую вы уже можете достичь.

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

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

Вот некоторые C# код, который должен решить проблему в данный момент времени:

int[] FindSubsetToImpliedTarget(int[] inputs) { 
    var target = 100*(int)Math.Ceiling(Math.Sqrt(inputs.Count)); 

    // build up how-X-was-reached table 
    var reached = new int?[target+1]; 
    reached[0] = 0; // the empty set reaches 0 
    foreach (var e in inputs) { 
     // we go backwards to avoid reaching off of ourselves 
     for (var i = target; i >= e; i--) { 
      if (reached[i-e].HasValue) { 
       reached[i] = e; 
      } 
     } 
    } 

    // was target even reached? 
    if (!reached[target].HasValue) return null; 

    // build result by back-tracking via the logged reached values 
    var result = new List<int>(); 
    for (var i = target; reached[i] != 0; i -= reached[i].Value) { 
     result.Add(reached[i].Value); 
    } 
    return result.ToArray(); 
} 

Я не тестировал код выше, так что будьте осторожны опечаток и офф-на-онов.

Answer 2

Ok следующее простое решение в O (n) времени.

Поскольку требуемая сумма S составляет порядка O(n^0.5), если мы сформулируем алгоритм сложности S^2, то мы хороши, так как наш алгоритм должен быть эффективной сложности O(n).

1. Повторяйте один раз по всем элементам и проверьте, меньше ли значение S или нет. Если это тогда, то нажмите его в новом массиве. Этот массив должен содержать максимум S элементов (O (n^.5))

2. Сортируйте этот массив в порядке убывания в O (sqrt (n) * logn) времени (< O (n)). Это происходит потому, что logn < = sqrt (n) для всех натуральных чисел. https://math.stackexchange.com/questions/65793/how-to-prove-log-n-leq-sqrt-n-over-natural-numbers

Теперь эта проблема является проблемой ранца 1D с W = S и числа элементов = S (верхняя граница).

Максимально общий вес предметов и посмотреть, если она равна С.

Она может быть решена с использованием динамического программирования в линейное время (линейный WRT Вт ~ S).

Answer 3

С типичным алгоритмом DP для subset-sum problem получите O(N) алгоритм, требующий много времени. Мы используем dp[i][k] (Boolean), чтобы указать, является ли первое, что я элементы имеют подмножество с суммой к, уравнение перехода:

dp[i][k] = (dp[i-1][k-v[i] || dp[i-1][k]), 

это O(NM), где N является размер набора и М представляет собой целевой суммы. Поскольку элементы различны, а сумма должна быть равна 100*ceil(n^.5), нам просто нужно рассмотреть не более первых элементов 100 * ceil (n^.5), тогда мы получим N<=100*ceil(n^.5) и M = 100*ceil(n^.5).

Алгоритм DP является O(N*M) = O(100*ceil(n^.5) * 100*ceil(n^.5)) = O(n).