在我的程序中,我将有多个数组,每个数组包含大约 40 000 个字符串,每个字符串的长度不同(从 10 到 5000 个字符),我需要将这个数组发送到一次只接受 5 000 个字符的 API。
为了进行最少的 API 调用,我需要找到每次发送的最佳字符串组合。
例如,如果我得到一个长度不同的数组 {3, 5, 10, 3, 4, 1, 4} 并且 api 的最大长度是 10。它应该返回 {10},{4 1 5} , {3 3 4}。
我一直在寻找不同的算法,但似乎没有一个能满足我的需要。 (子集和等)
非常感谢任何帮助!
最佳答案
你的问题是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:
插入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]]
此外,您可能对 wiki 页面上的“精确算法”部分感兴趣。
关于arrays - 对 API 进行最少调用的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28931137/