动态规划:找出所有成员的乘积等于给定数的子集

Question

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

输入：n个整数和数字k的数组

我们必须从数组中找到一组数字，集合中所有这些数字的乘积等于k就是

我想，我必须使用动态编程来完成这项任务。但我不知道如何使用它。

Answer 1

这类似于子集求和问题，在该问题中，您需要找到求和为值k的子集。

由于你的问题有一个解决方案（你有一个子集S，乘法是k），当且仅当你对集合中的每个x都有log（x）的子集，其和是log(k)（相同的子集，每个元素上有log），所以问题几乎是相同的。

然而，通常使用的DP解决方案对求和非常有效，因为元素的和不会很大，而乘法会很大。您也不能对所有元素使用log并"使用它"，因为数字不会是整数，并且子集和的DP解决方案需要整数来处理。

但是，您可以使用Top-Down-DP（记忆）部分解决此问题。这相当简单，具体操作如下：

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()) 调用