Вопросы на собеседовании #5

« На углу двое юношей возились с каким-то механическим устройством. Один убежденно говорил: «Конструкторская мысль не может стоять на месте. Это закон развития общества. Мы изобретём его. Обязательно изобретём. Вопреки бюрократам вроде Чинушина и консерваторам вроде Твердолобова». Другой юноша нёс свое: «Я нашел, как применить здесь нестирающиеся шины из полиструктурного волокна с вырожденными аминными связями и неполными кислородными группами. Но я не знаю пока, как использовать регенерирующий реактор на субтепловых нейтронах. Миша, Мишок! Как быть с реактором?» Присмотревшись к устройству, я без труда узнал велосипед.

»

— Братья Стругацкие, «Понедельник начинается в субботу»

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

Задача

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

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

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

Первый алгоритм был твердолобый: next_permutation и суммирующий цикл по перестановке без всяких оптимизаций, так что, что-то вроде O(N * N!) я получил %)

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

def solve(k, a):
 s = sum(a)

 if s == k:
  return True
 elif s < k:
  return False
 elif len(a) == 1:
  return False
 else:
  for i in range(len(a)):
   temp = a[:i] + a[i+1:]
   if solve(k, temp):
    return True
 return False

Можно конечно еще кое-что оптимизировать , но суть от этого не поменяется.

А вообще это не "чистый" рюкзак, а скорее одна из подзадач из криптографического его применения, так как надо установить только факт наличия такой выборки. Почитав теорию, нашел решение в ДП. Сложность O(|a| * k). Вот код:

def solve(k, a):
 b = []
 for i in range(len(a)):
  b.append([None]*(k+1))
  
 b[0][0] = 1
 b[0][a[0]] = 1

 for i in range(1, len(a)):
  for j in range(k+1):
   if b[i-1][j]:
    b[i][j] = 1 # not include current
    if j + a[i] <= k:
     b[i][j + a[i]] = 1 #include current
     
 return bool(b[-1][-1])

А в некоторых случаях может быть эффективно следующее решение за O(2^|a|):

def solve(k, a):
 b = set()
 b.add(0)
 b.add(a[0])
 
 for i in range(1, len(a)):
  tmp = set()
  for j in b:
   tmp.add(j)
   if j + a[i] <= k:
    tmp.add(j + a[i])
  b = tmp

 return k in b

Вообще тема оказалась интересной, по теме можно почитать вики 1 2 3.

И все же как посчитать сложность в первом приложенном коде?

Другие части цикла: #1 #2 #3 #4