algorithm - 在数组中查找乘积等于给定数字的 k 个元素

Question

给定一个包含n 个非负整数和两个整数k 和m 的数组a，找到 a 的 k 个元素，其乘积等于 m(返回它们的索引)。输入保证有解。

所以蛮力算法会检查所有可能的组合，这是 O(n!/(k!(n-k)!)) 性能，但时间限制表明存在 O(n log n) 解决方案，我正在努力寻找。

Answer 1

如评论中所述，这可以通过动态规划来解决。

动态规划有两种方法。自上而下，自下而上。权衡是自上而下更容易做到。但自下而上往往可以表现得更好。由于您正在努力寻找解决方案，我将自上而下地进行解释。

要做top down，需要写一个递归算法，然后memoize .内存意味着如果你必须计算一个结果，你将它保存在缓存中。下次不做计算时，直接返回缓存的值即可。所以你采用了这样的函数:

def foo(bar, baz):
    # do recursive stuff
    return answer

然后把它变成这样:

cached_foo = {}
def foo (bar, baz):
    if (bar, baz) not in cached_foo:
        # Do recursive stuff
        cached_foo[(bar, baz)] = answer
    return cached_foo[(bar, baz)]

实践中可能会出现一些复杂情况，但这始终是总体思路。

在这种情况下，递归算法的核心是:

def reachable_factors(a, m, i, j):
    # Returns all factors of m that can be reached, and how to reach
    # them with j of the first i terms of a
    pass

这个算法应该很慢。但是一旦你记住它，它就会很快。

---

由于已经发布了另一个解决方案，这里是一个 Python 解决方案。

def exact_factorization(a, m, k):
    cache = {}
    def reachable_factors(i, j):
        # This will be all of the ways to get to a factor of m
        # using j of the first i elements of a
        if (i, j) not in cache:
            # This is the recursive calculation
            answer = {}
            if i < j:
                # We cannot use more than i of the first i elements.
                pass
            elif 0 == j:
                # The empty product is 1
                answer = {1: None}
            else:
                # First, find all of the ways of not using this element.
                for (fact, path) in reachable_factors(i-1, j).iteritems():
                    answer[fact] = path

                # Note the potential off by one error.  The i'th
                # element is at i-1
                i_th = a[i-1]

                # Next,find all of the ways of using this element
                for (fact, path) in reachable_factors(i-1, j-1).iteritems():
                    if 0 == m % (fact * i_th):
                        answer[fact * i_th] = [i-1, path]

            cache[(i, j)] = answer
        return cache[(i, j)]

    reachable = reachable_factors(len(a), k)

    # The answer is now in reachable[m], but as a nested list in reverse
    # order.  We want to extract it in a better format.
    path = reachable[m]
    final_answer = []
    while path is not None:
        final_answer.append(path[0])
        path = path[1]
    return [x for x in reversed(final_answer)]

print(exact_factorization(
    [1, 2, 3, 2, 1, 4, 12], 12, 4
))

---

这是自下而上的方法。请注意，它的性能与自上而下相同，但需要的内存更少。它还避免了 Python 愚蠢的递归限制。

def exact_factorization(a, m, k):
    partial_answers = [{1: None}]
    for _ in range(k):
        partial_answers.append({})

    for i in range(len(a)):
        x = a[i]
        for j in range(k, 0, -1):
            these_answers = partial_answers[j]
            for fact, path in partial_answers[j-1].iteritems():
                if 0 == m % (x * fact):
                    these_answers[x * fact] = [i, path]

    reachable = partial_answers[k]

    if m not in reachable:
        return None

    # The answer is now in reachable[m], but as a nested list in reverse
    # order.  We want to extract it in a better format.
    path = reachable[m]
    final_answer = []
    while path is not None:
        final_answer.append(path[0])
        path = path[1]
    return [x for x in reversed(final_answer)]