对 API 进行最少调用的算法

Question

在我的程序中，我将有多个数组，其中包含大约 40 000 个字符串，每个字符串具有不同的长度（从 10 到 5000 个字符），我需要将这个数组发送到一个 API，它只接受 5 000 个字符一次。

为了进行最少的 API 调用，我需要找到每次发送的最佳字符串组合。

例如，如果我得到一个长度不同的数组 {3, 5, 10, 3, 4, 1, 4} 并且 api 的最大长度是 10。它应该 returns {10}，{4 1 5}，{3 3 4}。

我一直在寻找不同的算法，但似乎没有一个能满足我的需要。（子集和其他）

非常感谢任何帮助！

Answer 1

绝对看起来像一个动态规划问题。您的问题与 Subset Sum problem 类似，不同之处在于您想要 return 所有此类子集，而不是仅仅查找是否存在这样的子集。

这个 link 似乎接近您的需要： http://www.careercup.com/question?id=12899672

动态编程通常很难让您全神贯注。我希望其他人能提供详尽的解释（对我也是如此），但希望这能给你一个开始的地方。

Answer 2

这是动态规划问题（子集求和问题）的变体。我们不仅要查找总和是否存在，而且还要查找所有不同的子集。

我们构建了 sum(rows) - vs - number(cols) 的二维布尔查找 table，这在许多 DP 问题中都是典型的。为了找到与总和完全匹配的子集，我们可以在查找时调用以下回溯函数 table 以找到可能的有效总和。

bool backtrack(bool **subset, int sum, int a[], int n) {
    if(sum == 0) { // Sum possible
        return true;
    }
    if(sum < 0) { //Sum not possible
        return false;
    }

    for(int j=1; j<=n; j++) {
        if(subset[sum][j] == true) {
            int val = a[j-1];

            // If val is included, can we have a valid sum?
            bool valid = backtrack(subset, sum-val, a, j-1);
            if(valid == true) {
                printf("%d ", val);
                return true;
            }
        }
    }
    return false;
}

我们可以这样调用上面的函数，打印出数字组合，每行一个组合-

for(j=1; j<=n; j++) {
    if(subset[sum][j] == 1) { //For every col which is =1 for the sum'th row
       bool valid = backtrack(subset, sum-a[j-1], a, j-1);
       if(valid) {
          printf("%d\n", a[j-1]);
       }
    }
}

Answer 3

这对您有何帮助？显然，您可以将最大值更改为您想要的任何值，并且可能将其更改为从调用函数中设置，但我会将这些选择留给您。

这对我有用，如果您有任何问题，请告诉我。

List<List<string>> Chunk(List<string> inputStrings)
{
    List<List<string>> retVal = new List<List<string>>();

    List<string> sortedStrings = inputStrings.OrderByDescending(s => s.Length).ToList();

    while (sortedStrings.Any())
    {
        List<string> set = new List<string>();
        int max = 10;

        for (int i = 0; i < sortedStrings.Count(); ++i)
        {
            if (max == 0)
                break;
            if (max - sortedStrings[i].Length < 0)
                continue;

            set.Add(sortedStrings[i]);
            max -= sortedStrings[i].Length;
            sortedStrings.RemoveAt(i);
            --i;
        }

        if(set.Any())
            retVal.Add(set);
    }

    return retVal;
}

注意：这是 C#。如果需要，我可以用另一种语言或使用不同的数据结构重做。

Answer 4

你的问题是 Bin Packing problem. Please find pretty nice solution in following paper: A new algorithm for optimal bin packing 作者 Richard Korf（请参阅此处的示例问题）

让我们看看数组的例子：

MAXSIZE=20
[1 2 4 5 7 10 11]

使用参考论文中的算法，您将得到：

[11 4 5] [10 7 2 1]

简而言之，此算法通过以下方式构建 bin：

插入 bin 最大元素
搜索适合左侧体积的所有元素并最大化它们的总和

例如，在我们的案例中，第一步是：

# Take max element
[11]
# We have 9 volume left
# All smaller are [1 2 4 5 7] - greedy would take 7 in this case
# 4 and 5 sums up to 9 which is best fit in this case so first bin become:
[11 5 4]
# Next step: take max
[10]
# we have 10 volume left. elements lower than 10:
# [1 2 7]
# this sums up to 10 in this case giving second bin
[10 7 2 1]

还有一些贪心与提到的示例：

ARR = [3, 3, 5, 5, 5, 5, 14]
BINSIZE = 20
Greedy result:
Size 3:
[[14, 5], [5, 5, 5, 3], [3]]
Mentioned alg result (size 2):
[[14, 3, 3], [5, 5, 5, 5]]

此外，您可能对维基页面上的 'Exact algorithm' 部分感兴趣。

Answer 5

这似乎是通过贪婪算法解决的，而不是应该在将字符串发送到 API 之前执行的回溯算法。

对 API 进行最少调用的算法

Algorithm to make the fewest call to an API

arrays

api

algorithm