动态编程：找到所有成员乘积等于给定数的子集 [英] Dynamic programming: find the subset with product of all members is equals to given number

问题描述

我将找到解决该问题的算法。

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

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

我认为，必须为此任务使用动态编程。但是我不知道如何使用它。

解决方案

这类似于子集和问题，需要您找出总和为值 k 的子集。

因为有解决问题的方法（您有一个子集 S ，其乘积为 k ），且仅当每个x中都有log（x）子集时集合的总和为 log（k）（相同的子集，每个元素上都有 log ），问题几乎是相同的。

但是，通常使用的DP解决方案对求和非常有效，因为元素的总和不会趋于庞大，而乘以却很。您也不能在所有元素上都使用 log 并使用它，因为数字将不是整数-子集总和的DP解决方案要求使用整数。 / p>

但是，您可以使用部分解决此问题自上而下的DP（内存） 。这是相当简单的，其操作如下：

  existenceOfSubset（set，product，map）：
 if（product == 1）：
返回true 
 if（set.isEmpty（））：
返回false 
 if（map.containsKey（product））：
返回map .get（产品）
 first = set.getFirst（）
 set = set.removeFirst（）
解决方案= existOfSubset（set，product，map）OR（product％first == 0？ existOfSubset（set，product / first，map）：false）//两种可能性的递归步骤
 map.put（product，solution //存储
 set.addFirst（first）//清理
返回解决方案
  

使用 existenceOfSubset（set，product，new HashMap（ ））

I will find an algorithm for this problem.

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

I think, I must use dynamic programming for this task. But I have no idea, how to use it.

解决方案

This is similar to the subset sum problem, where you are required to find a subset whom sum is a value k.

Since there is a solution to your problem (you have a subset S whom multiplication is k) if and only if you have a subset of log(x) for each x in the set, whom sum is log(k) (the same subset, with log on each element), the problems are pretty much identical.

However, the DP solution generally used is very efficient for sums, since sum of elements don't tend to end up huge, while multiplying does. You also cannot take log on all elements and "work with it", because the numbers will not be integers - and the DP solution to subset sum requires integers to work on.

However, you can partially solve this issue by using Top-Down DP (memoization). This is fairly simple and is done as follows:

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

invoke with existenceOfSubset(set,product,new HashMap())

这篇关于动态编程：找到所有成员乘积等于给定数的子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！