动态编程:找到所有成员的乘积等于给定数的子集

Question

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

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

我们必须从数组中找到一组数字,所有这些数字在set中的乘积等于k

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

Answer 1

这类似于子集求和问题,您需要找到sum为值的子集k.

因为有一个解决你的问题的方法(你有一个S乘法的子集k)当且仅当你有一个集合中每个x的log(x)的子集时,sum是log(k)(相同的子集,log每个元素都有) ,问题几乎完全相同.

然而,通常使用的DP解决方案对于总和来说是非常有效的,因为元素的总和不会最终变大,而乘法也是如此.你也不能接受log所有元素并"使用它",因为数字不是整数 - 并且DP解决方案的子集和需要整数来处理.

但是,您可以使用自上而下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())