用于最少调用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问题.请在下面的论文中找到非常好的解决方案: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页面上的"精确算法"部分感兴趣.