动态规划：找到所有成员的乘积等于给定数字的子集

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 和 "work with it"，因为数字不是整数 - 子集总和的 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())

动态规划：找到所有成员的乘积等于给定数字的子集

Dynamic programming: find the subset with product of all members is equals to given number

algorithm

dynamic-programming