这个过程的计算“内循环”是计算平均成本。也就是说，给定一组四个数据包大小，计算每个订单所需的平均数据包数量。一种称为动态编程的技术非常适合此目的。看看你是否能理解它是如何工作的。
以下是一种动态编程方法的高级伪代码。
目标：给定四个大小 1、s1、s2、s3，求每个订单的成本。
关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您正在帮助确保有关塑造当今世界的发现和想法的具有影响力的故事的未来。
创建一个大小为 80 的数组。（这将是您的成本数组。）将每个条目初始化为具有无限成本，除了位置 1、s1、s2 和 s3 的条目，您将它们的成本赋值为 1。
对于条目 i = 2 到 80
如果 cost(i) == 无穷大
对于条目 j 从 1 到 i-1
如果 (cost(j) + cost(i-j)) < cost(i)
cost(i) := (cost(j) + cost(i-j))
结束 如果
结束 对于
结束 如果
结束 对于
将所有成本求和并除以 80 以获得平均成本
让我们用文字看看发生了什么：假设您正在测试数据包大小 1、5、10 和 14。最初，cost(1) = 1，cost(5) = 1，cost(10) = 1，cost(14) = 1。所有其他成本都是无限的。现在从 i = 2 开始。此时，cost(2) = 无穷大，因此语句“如果 cost(i) == 无穷大”为真。然后我们查看 j 从 1 到 2 – 1。这只剩下 j = 1，我们测试 cost(2) 是否大于 cost(1) + cost(2-1) = cost(1) + cost(1) = 1 + 1 = 2。因为 cost(2) 目前是无穷大，所以该测试成功。因此 cost(2) 的值为 2（这就是当 i 为 2 且 j 为 1 时“cost(i) := (cost(j) + cost(i-j))”的含义），这是两个单单元数据包的成本。看看您是否可以继续这种模式。
既然您知道如何评估给定的候选数据包大小集，那么剩下的就是遍历不同的数据包大小三元组可能性，以找到最佳的数据包大小集。
1. 当 1 到 80 之间的所有数量的可能性相等时，一个好的数据包大小集是：1 5 18 25，每个请求的平均成本低于 3.7 个数据包。
2. 相同的动态编程方法也适用于此问题，但成本函数必须有所改变，以反映不同大小订单的可能性变化。一种方法是将 10 到 20 之间的订单（包括 10 和 20）的成本乘以 4。这将反映这些订单频率的增加。要获得最佳平均值，请将总成本除以 113（80 + (3*11)）。否则，过程不会发生任何变化。一个好的数据包大小集（实际上是最好的之一）是 1、10、13 和 17。平均所需的数据包数量低于 3.5。你能找到其他的吗？