Быстрое решение для суммы подмножества

Ответ 1

В то время как мой предыдущий ответ описывает алгоритм приближения polytime к этой проблеме, запрос был специально сделан для реализации Picser polytime dynamic programming solution, когда все x _i в x положительны:

from bisect import bisect

def balsub(X,c):
    """ Simple impl. of Pisinger generalization of KP for subset sum problems
    satisfying xi >= 0, for all xi in X. Returns the state array "st", which may
    be used to determine if an optimal solution exists to this subproblem of SSP.
    """
    if not X:
        return False
    X = sorted(X)
    n = len(X)
    b = bisect(X,c)
    r = X[-1]
    w_sum = sum(X[:b])
    stm1 = {}
    st = {}
    for u in range(c-r+1,c+1):
        stm1[u] = 0
    for u in range(c+1,c+r+1):
        stm1[u] = 1
    stm1[w_sum] = b
    for t in range(b,n+1):
        for u in range(c-r+1,c+r+1):
            st[u] = stm1[u]
        for u in range(c-r+1,c+1):
            u_tick = u + X[t-1]
            st[u_tick] = max(st[u_tick],stm1[u])
        for u in reversed(range(c+1,c+X[t-1]+1)):
            for j in reversed(range(stm1[u],st[u])):
                u_tick = u - X[j-1]
                st[u_tick] = max(st[u_tick],j)
    return st

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

Ответ 2

Я уважаю готовность, с которой вы пытаетесь решить эту проблему! К сожалению, вы пытаетесь решить проблему с NP-полным, что означает, что любое дальнейшее улучшение, которое нарушает полиномиальный временной барьер, будет доказать, что P = NP.

Реализация, которую вы вытащили из Hacker News, по-видимому, согласуется с решением для псевдо-полиномиального динамического программирования, где любые дополнительные улучшения должны определение прогресса текущего состояния этой проблемы и всех ее алгоритмических изоформ. Другими словами: хотя возможно постоянное ускорение, вы вряд ли увидите алгоритмическое улучшение этого решения проблемы в контексте этого потока.

Однако вы можете использовать приблизительный алгоритм, если вам требуется решение polytime с допустимой степенью ошибки. В псевдокоде, явно украденном из Википедии, это будет:

initialize a list S to contain one element 0.
 for each i from 1 to N do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/N < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

Реализация Python, максимально сохраняющая исходные термины:

from bisect import bisect

def ssum(X,c,s):
    """ Simple impl. of the polytime approximate subset sum algorithm 
    Returns True if the subset exists within our given error; False otherwise 
    """
    S = [0]
    N = len(X)
    for xi in X:
        T = [xi + y for y in S]
        U = set().union(T,S)
        U = sorted(U) # Coercion to list
        S = []
        y = U[0]
        S.append(y)
        for z in U: 
            if y + (c*s)/N < z and z <= s:
                y = z
                S.append(z)
    if not c: # For zero error, check equivalence
        return S[bisect(S,s)-1] == s
    return bisect(S,(1-c)*s) != bisect(S,s)

... где X - ваша сумка терминов, c - ваша точность (от 0 до 1), а s - целевая сумма.

Подробнее см. статью в Википедии.

(Дополнительная ссылка, дальнейшее чтение на CSTheory.SE)

Ответ 3

Я не знаю много питона, но есть подход, называемый встречей посередине. Псевдокод:

Divide activities into two subarrays, A1 and A2
for both A1 and A2, calculate subsets hashes, H1 and H2, the way You do it in Your question.
for each (cost, a1) in H1
     if(H2.contains(-cost))
         return a1 + H2[-cost];

Это позволит вам удвоить количество элементов деятельности, которые вы можете обрабатывать в разумные сроки.

Ответ 4

Извиняюсь за "обсуждение" проблемы, но проблема "Subset Sum", где значения x ограничены, не является NP-версией проблемы. Динамические программные решения известны ограниченными задачами x. Это делается путем представления значений x в виде суммы единичных длин. В решениях динамического программирования имеется ряд фундаментальных итераций, линейных с этой общей длиной x. Тем не менее, подмножество Sum находится в NP, когда точность чисел равна N. То есть, число или основание 2 значения места, необходимые для обозначения x = N. Для N = 40 x должно быть в миллиардах. В NP-задаче длина единицы x возрастает экспоненциально с N. Поэтому решения динамического программирования не являются полиномиальным временным решением проблемы суммы подмножеств NP. В этом случае все еще существуют практические примеры проблемы подмножества Sum, где x ограничены и решение динамического программирования действительно.

Ответ 5

Вот три способа сделать код более эффективным:

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

• Для каждой деятельности словарь заселен старым содержимым (подмножества [prev_sum] = подмножество). Быстрое увеличение простого словаря

• Разделение значений в два и применение встречного в среднем подходе.

Применение первых двух оптимизаций приводит к следующему коду, который более чем в 5 раз быстрее:

def subset_summing_to_zero2 (activities):
  subsets = {0:-1}
  for (activity, cost) in activities.iteritems():
      for prev_sum in subsets.keys():
          new_sum = prev_sum + cost
          if 0 == new_sum:
              new_subset = [activity]
              while prev_sum:
                  activity = subsets[prev_sum]
                  new_subset.append(activity)
                  prev_sum -= activities[activity]
              return sorted(new_subset)
          if new_sum in subsets: continue
          subsets[new_sum] = activity
  return []

Также применяя третьи результаты оптимизации в чем-то вроде:

def subset_summing_to_zero3 (activities):
  A=activities.items()
  mid=len(A)//2
  def make_subsets(A):
      subsets = {0:-1}
      for (activity, cost) in A:
          for prev_sum in subsets.keys():
              new_sum = prev_sum + cost
              if new_sum and new_sum in subsets: continue
              subsets[new_sum] = activity
      return subsets
  subsets = make_subsets(A[:mid])
  subsets2 = make_subsets(A[mid:])

  def follow_trail(new_subset,subsets,s):
      while s:
         activity = subsets[s]
         new_subset.append(activity)
         s -= activities[activity]

  new_subset=[]
  for s in subsets:
      if -s in subsets2:
          follow_trail(new_subset,subsets,s)
          follow_trail(new_subset,subsets2,-s)
          if len(new_subset):
              break
  return sorted(new_subset)

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

Для нижней границы (например, bound = 1000 и n = 300) встреча в середине только получает коэффициент около 2 улучшения другого первого улучшенного метода. Это связано с тем, что словарь подмножеств плотно заселен.

Однако для высокой границы (например, bound = 100,000 и n = 30) встреча в середине занимает 0,03 секунды по сравнению с 2,5 секундами для первого улучшенного метода (и 18 секунд для исходного кода)

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

Может показаться удивительным, что встречаться посередине только в два раза быстрее для низких границ. Причина в том, что количество операций на каждой итерации зависит от количества ключей в словаре. После добавления k действий мы могли бы ожидать, что там будет 2 ** k ключа, но если привязка будет мала, тогда многие из этих клавиш будут сталкиваться, поэтому вместо них будут только ключи O (bound.k).

Ответ 6

Думаю, что я поделился бы с моим решением Scala для обсуждаемого алгоритма псевдополиэтни, описанного в Википедии. Это слегка измененная версия: она определяет количество уникальных подмножеств. Это очень связано с проблемой HackerRank, описанной в https://www.hackerrank.com/challenges/functional-programming-the-sums-of-powers. Стиль кодирования не может быть отличным, я все еще участвую Scala:) Может быть, это по-прежнему полезно для кого-то.

object Solution extends App {
    var input = "1000\n2"

    System.setIn(new ByteArrayInputStream(input.getBytes()))        

    println(calculateNumberOfWays(readInt, readInt))

    def calculateNumberOfWays(X: Int, N: Int) = {
            val maxValue = Math.pow(X, 1.0/N).toInt

            val listOfValues = (1 until maxValue + 1).toList

            val listOfPowers = listOfValues.map(value => Math.pow(value, N).toInt)

            val lists = (0 until maxValue).toList.foldLeft(List(List(0)): List[List[Int]]) ((newList, i) => 
                    newList :+ (newList.last union (newList.last.map(y => y + listOfPowers.apply(i)).filter(z => z <= X)))
            )

            lists.last.count(_ == X)        

    }
}