algorithm - 数组中最接近的乘法值

Question

我有一个整数数组，并且给定了一个数字 K，我需要找到最接近 K 的值(也是数组的元素)，该值可以通过将数组中的各种数字相乘生成。

例如。 到达 - 2, 2, 5, 5, 7 K = 30

输出 - 2*2*7 = 28。

我想不出比指数算法更好的解决方案了，在指数算法中我对元素进行不同的排列并检查最接近的值。请提出一个更好的(可能是动态规划)方法来有效地解决它。

这是我写的:-

void findClosestValue(int arr[], int start, int end, int k, int& diff, int mul)
{
    if(start<=end+1)
    {
        cout<<"  start = "<<start<<"  end = "<<end<<"  diff = "<<diff<<"  k = "<<k<<"  mul = "<<mul<<endl;
        if(diff > differ(k, mul))
            diff = differ(k, mul);
        findClosestValue(arr, start+1, end, k, diff, mul*arr[start]);
        findClosestValue(arr, start+1, end, k, diff, mul);
    }
    else
        return;
}

调用这个函数是:-

整数值 = 100000000;

findClosestValue(arr, 0, size-1, k, val, 1);

Answer 1

这绝对是一个动态规划问题，但是有一些技巧。

您需要建立一个表格，按您可以达到的产品列出您第一次达到该值时需要的最后一个因素的位置。 (换句话说，如果您发现有两种方法可以达到某个值，您希望坚持使用第一种。)您可以使用动态规划构建此表。

在您的 [2, 2, 5, 5, 7] 示例中，位置从 0 到 4 该表看起来像这个:

{
    1: -1,
    2: 0,
    4: 1,
    5: 2,
    10: 2,
    20: 2,
    50: 3,
    100: 3,
    7: 4,
    14: 4,
    28: 4,
    35: 4,
    70: 4,
    140: 4,
    350: 4,
    700: 4
}

现在您搜索表格以找到最接近的值。即 28。

现在你倒着读这些因素。你得到 28 位置 4，也就是 7。除以那个，你在 1 的位置有 4，也就是 2。除以那个，你在 0 位置有 2，也就是 2。最后当你开始时你有 1。 (空积始终为 1。)

这个解决方案几乎有效。问题是您的表通常会变得非常大，并且几乎完全被太大的值填满。鉴于整数的限制，您应该跟踪您达到的大于目标答案绝对值的最小绝对值。在这种情况下，您的表格将缩减为:

{
    1: -1,
    2: 0,
    4: 1,
    5: 2,
    10: 2,
    20: 2,
    50: 3,
    7: 4,
    14: 4,
    28: 4,
    35: 4
}

这里没有那么大的胜利。但是对于更大的集合，这将提供显着的改进。