arrays - 对 API 进行最少调用的算法

Question

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

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

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

我一直在寻找不同的算法，但似乎没有一个能满足我的需要。 (子集和等)

非常感谢任何帮助!

Answer 1

你的问题是Bin Packing problem .请在以下论文中找到非常好的解决方案: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:

1. 插入bin最大元素

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

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

# 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]]

此外，您可能对 wiki 页面上的“精确算法”部分感兴趣。