Динамическое программирование: найти подмножество с произведением всех членов равно заданному числу

Question

Я найду алгоритм для решения этой проблемы.

Вход: массив из п целых чисел и число к

Мы должны найти набор чисел из массива, что произведение всех этих чисел в наборе равна K является

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

Answer 1

Это похоже на проблему суммы подмножества, в которой вам необходимо найти подмножество, сумма которого равна k.

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

Однако решение DP, которое обычно используется, очень эффективно для сумм, поскольку сумма элементов не имеет тенденций в конечном итоге огромную, а умножение -. Вы также не можете принимать log по всем элементам и «работать с ним», потому что числа не будут целыми числами, а для решения DP для подмножества суммы требуются целые числа.

Однако вы можете частично решить эту проблему, используя Top-Down DP (memoization). Это довольно просто и делается следующим образом:

existenceOfSubset(set, sum, map): 
    if (sum == 1): 
      return true 
    if (set.isEmpty()): 
      return false 
    if (map.containsKey(sum)): 
      return map.get(sum) 
    first = set.getFirst() 
    set= set.removeFirst() 
    sol = existenceOfSubset(set,sum,map) OR (sum%first == 0?existenceOfSubset(set,sum/first,map):false) //recursive step for two possibilities 
    map.put(sum,sol) //memorize 
    set.addFirst(first) //clean up 
    return sol 

вызова с existenceOfSubset(set,sum,new HashMap())