0

我相信这更像是一个算法问题，但我也想在 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[] 组合？

可以将两个函数假定为线性函数。即两个里程函数的返回值是具有（不同）负斜率和（不同）偏移的线性函数。

所以我需要找到的是这样的：

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

谢谢你。

4

2 回答 2

1

我可以建议以下解决方案：

组合总数为 2^（权重数）。使用位逻辑，我们可以遍历所有组合并计算 maxDistance。组合值中的位显示哪个重量分配给哪个车辆。

请注意，算法复杂度是指数级的，并且int位数有限！

float maxDistance = 0.f;

for (int combination = 0; combination < (1 << ARRAYSIZE(weights)); ++combination)
{
    int weightForVehicleONE = 0;
    int weightForVehicleTWO = 0;

    for (int i = 0; i < ARRAYSIZE(weights); ++i)
    {
        if (combination & (1 << i)) // bit is set to 1 and goes to vechicleTWO
        {
            weightForVehicleTWO += weights[i];
        }
        else // bit is set to 0 and goes to vechicleONE
        {
            weightForVehicleONE += weights[i];
        }
    }

    maxDistance = max(maxDistance, min(vehicelONEMileage(weightForVehicleONE), vehicleTWOMileage(weightForVehicleTWO)));
}
于 2013-09-04T06:52:13.333 回答
1
  • 这应该在 cs 或数学网站上。
  • 简化：假设我们可以线性分配权重，而不是对象数组。

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

在下文中，我们将所有权重的总和缩放为1。因此，类似这样的分布(0.7, 0.3)意味着 70% 的重量装载在车辆 1 上。我们称车辆 1x的负载和车辆的负载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)

  • 第一个，如果加载到一号车上，给你的分布比一号车上的预期略少。

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

我把 C++ 部分留给你。;-)

于 2013-09-04T09:03:42.397 回答