C++:查找可分为两组的数组项的所有组合

Question

我认为这更像是一个算法问题，但我也想用 C++ 来做。 让我用一个例子来说明这个问题。

假设我有 N 个对象(不是编程对象)，每个对象具有不同的权重。我有两辆车可以载他们。这些车辆足够大，可以单独运载所有元素。这两辆车有自己的里程数和不同的油箱燃油量。里程数也取决于它承载的重量。

目标是让这N个物体尽可能远。所以我需要在两辆车之间以某种方式分配 N 个对象。请注意，我不需要让它们保持“相同”的距离，而是尽可能远。例如，我希望两辆车分别行驶 5 公里和 6 公里，而不是一辆行驶 2 公里，另一辆行驶 7 公里。

我想不出一个理论上的封闭式计算来确定每辆车要装载的重量。因为记住我需要携带所有 N 个对象，这是一个固定值。

据我所知，我需要尝试所有的组合。

有人可以建议一种有效的算法来尝试所有组合吗？

例如我会有以下内容:

int weights[5] = {1,4,2,7,5}; // can be more values than 5
float vehicelONEMileage(int totalWeight);
float vehicleTWOMileage(int totalWeight);

我如何有效地尝试 weights[] 与这两个函数的所有组合？

这两个函数可以假设为线性函数。 IE。两个里程函数的返回值是具有(不同的)负斜率和(不同的)偏移量的线性函数。

所以我需要找到的是:

MAX(MIN(vehicleONEMileage(x), vehicleTWOMileage(sum(weights) - x)));

谢谢。

Answer 1

• 这应该在 cs 或 the math 网站上。
• 简化:假设我们可以线性分配权重，而不是一组对象。

我们要优化的函数是两个行程距离中的最小值。求最小值的最大值和求乘积的最大值是一样的(没有证明。但是看到这个，想想矩形的周长和面积的关系。给定周长，面积最大的矩形是正方形，它也恰好具有最大的最小边长)。

在下文中，我们会将所有权重的总和缩放到1。 .所以，像 (0.7, 0.3) 这样的分布表示所有重量的 70% 都加载在车辆 1 上。我们称车辆 1 的负载为 x和车辆的负载1-x .

给定两个线性函数 f = a x + b和 g = c x + d , 其中f是车辆1满载时的里程x , 和 g车辆 2 也一样，我们想要最大化

(a*x+b)*(c*(1-x)+d)

让我们让 Wolfram Alpha 为我们完成艰苦的工作:www.wolframalpha.com/input/?i=derive+%28%28a*x%2Bb%29*%28c*%281-x%29%2Bd% 29%29

它告诉我们在

处有一个极值

x_opt = (a * c + a * d - b * c) / (2 * a * c)

这就是您高效解决问题所需的一切。

完整算法:

• 查找 a , b , c , d

  b = vehicleONEMileage(0)

  a = (vehicleONEMileage(1) - b) * sum_of_all_weights

  c 相同和 d

• 计算 x_opt如上。

  • 如果x_opt < 0 , 将所有重量加载到车辆 2 上
  • 如果x_opt > 1 , 将所有重量加载到车辆 1 上
  • 否则，尝试加载tgt_load = x_opt*sum_of_all_weights上车 1，其余上车 2。

• 剩下的就是背包问题了。参见 http://en.wikipedia.org/wiki/Knapsack_problem#0.2F1_Knapsack_Problem

  如何应用？使用那里描述的动态编程算法两次。

  • 最大负载为 tgt_load
  • 将负载最大化到 ( sum_of_all_weights - tgt_load )

• 第一个，如果装载到车辆 1 上，给您的分布略低于车辆 1 的预期。

• 第二个，如果装在第二辆车上，给你的分配比第二辆车上的预期略多。
• 其中之一是最佳解决方案。比较它们并使用更好的。

我将 C++ 部分留给您。 ;-)