algorithm - 动态规划 : find the subset with product of all members is equals to given number

Question

我会找到解决这个问题的算法。

Input: array of n integers and number k

We must find a set of numbers from array, that product of all this numbers in set equals to k is

我想，我必须为这个任务使用动态规划。但我不知道如何使用它。

Answer 1

这类似于子集求和问题，您需要找到一个子集，其求和值为 k。

因为你的问题有一个解决方案(你有一个子集 S，乘法是 k)当且仅当你有一个 log(x) 的子集集合中的每个 x，其总和为 log(k)(相同的子集，每个元素都有 log)，问题几乎相同。

但是，通常使用的 DP 解决方案对于求和非常有效，因为元素的总和往往不会很大，而相乘会。您也不能对所有元素采用 log 并“使用它”，因为数字不是整数 - 子集总和的 DP 解决方案需要整数才能处理。

但是，您可以使用 Top-Down DP (memoization) 部分解决此问题。 .这相当简单，按如下方式完成:

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

调用 existenceOfSubset(set,product,new HashMap())