时间戳

首页 > 解决方案 > 从给出所需系数的数字数组中找到组合

algorithm - 从给出所需系数的数字数组中找到组合

问题描述

请为此类任务推荐最佳算法或解决方案：

有几个带有小数的数组

a = [1.5, 2, 3, 4.5, 7, 10, ...(up to 100 numbers)]
b = [5, 6, 8, 14, ...]
c = [1, 2, 4, 6.25, 8.15 ...] (up to 7 arrays)

数组可以是任意长度并包含不同数量的数字。

需要从每个数组中选择一个数字，使其乘积在给定范围内。

例如数据所需的产品应该在 40 到 50 之间。解决方案可以是：

  1. a[2] * b[2] * c[1] = 3 * 8 * 2 = 48
  2. a[0] * b[3] * c[1] = 1.5 * 14 * 2 = 42

如果可以有多种解决方案（不同的组合），那么您如何以最佳方式找到它们？

标签： algorithmdata-structures

解决方案

这是可行的，但几乎没有。这将需要使用各种策略一遍又一遍地组合成对的事物。

首先，如果您有 2 个不超过 100 个事物的数组，您可以创建一个包含所有对的数组，按总和升序或降序排序，其中只有 10,000 个事物。

接下来，我们可以使用堆来实现优先级队列。

使用优先级队列，我们​​可以组合 2 个大小最多为 10,000 的有序数组，以升序或降序输出总和，同时不跟踪超过 10,000 个事物。如何？首先我们创建一个这样的数据结构：

Create priority queue
For every entry a of array A:
    Put (a, B[0], 0) into our queue using the product as a priority
return a data structure which contains B and the priority queue

现在我们可以像这样获取值：

If the priority queue is empty:
    We're done
else:
    Take the first element of the queue
    if not at the end of B:
        insert (a, b[next_index], next_index) into the queue
    return that first element

我们可以通过查看队列的第一个元素来查看它们，而无需触及数据结构。

该策略可以通过 2 个大小为 10,000 的阵列进行流式传输，总工作量仅为数十亿次操作。

好的，所以现在我们可以安排始终有 7 个数组。（有些可能只是微不足道的[1]。）我们可以从蛮力策略开始如下。

Combine the first 2 ascending.
Combine the second 2 ascending.
Combine the third 2 descending.
Arrange the last descending.

接下来我们可以使用优先队列合并策略如下：

Combine (first 2) with (second 2) ascending
Combine (third 2) with last descending

我们现在只需要生成器。

现在我们的策略将如下所示：

For each combination (in ascending order) from first 4:
    For each combination that lands in window from last 3:
        emit final combination

但是我们怎么做窗口呢？好吧，随着前 4 个组合的上升，最后 3 个必须落入的窗口下降。所以调整窗口看起来像这样：

while there is a next value and next value is large enough to fit in the window:
    Extract next value
    Add next value to end of window
while first value is too large for the window:
    remove first value from the window

（可变大小的数组，例如 Python 的List，可以分别执行这两种操作O(1)。）

所以我们的实际完成方式是：

For each combination (in ascending order) from first 4:
    adjust entries in window from last 3
    For each in window from last 3:
        emit final combination

这具有数十亿次操作的固定开销以及O(number of answers)实际发出组合的开销。这包括许多具有大约 10k 个项目的数据结构，以及一个最大大小为 100 万个项目的窗口，最大内存使用量为几百 MB。

推荐阅读