php - 具有特定标准的笛卡尔积

Question

我正在尝试查找笛卡尔积并附加特定条件。

我有四个小组，每个小组 25 人。每个人都有分数和价格。每个池中的每个人看起来都是这样。

[0] => array(
    "name" => "jacob",
    "price" => 15,
    "score" => 100
),
[1] => array(
    "name" => "daniel",
    "price" => 22,
    "score" => 200
)

我想找到最佳的人员组合，从每个池中选出一个人。但是，有一个上限价格，任何分组都不能超过某个价格。

我一直在搞乱笛卡尔和置换函数，似乎无法弄清楚如何做到这一点。我知道如何编写代码的唯一方法是嵌套 foreach 循环，但这非常费力。

如您所见，下面这段代码效率极低。特别是如果池增加!

foreach($poolA as $vA) {
   foreach($poolb as $vB) {
       foreach($poolC as $vC) {
            foreach($poolD as $vD) {

                // calculate total price and check if valid
                // calculate total score and check if greatest
                // if so, add to $greatest array

            }
        }
    }    
}      

我还以为我可以找到一种方法来计算总的价格/分数比率并将其用于我的优势，但我不知道我错过了什么。

Answer 1

正如 Barmar 指出的那样，对每个池中的人员进行排序允许您在总价格超过限制时提前停止循环，从而减少需要检查的案例数量。但是，应用此改进的渐近复杂度仍然为 O(n⁴)(其中 n 是池中的人数)。

我将概述一种具有更好渐近复杂性的替代方法，如下所示:

1. 构造一个池 X，其中包含所有对的人，其中一个来自池 A，另一个来自池 B。
2. 构造一个池 Y，其中包含所有对的人，其中一个来自池 C，另一个来自池 D。
3. 按总价对池 X 中的对进行排序。然后对于任何具有相同价格的对，保留得分最高的一对并丢弃剩余的对。
4. 按总价对池 Y 中的对进行排序。然后对于任何具有相同价格的对，保留得分最高的一对并丢弃剩余的对。
5. 使用两个指针进行循环以检查满足价格约束的所有可能组合，其中 head 指针从池 X 中的第一项开始，而tail 指针从池 Y 中的最后一项开始。下面给出了示例代码来说明这个循环是如何工作的:

============================================= ===========================

$head = 0;
$tail = sizeof($poolY) - 1;

while ($head < sizeof($poolX) && $tail >= 0) {
    $total_price = $poolX[$head].price + $poolY[$tail].price;

    // Your logic goes here...

    if ($total_price > $price_limit) {
        $tail--;
    } else if ($total_price < $price_limit) {
        $head++;
    } else {
        $head++;
        $tail--;
    }
}

for ($i = $head; $i < sizeof($poolX); $i++) {
    // Your logic goes here...
}

for ($i = $tail; $i >= 0; $i--) {
    // Your logic goes here...
}

============================================= ===========================

步骤1和2的复杂度是O(n²)，步骤3和4的复杂度可以在O(n² log(n )) 使用平衡二叉树。而第5步本质上是对n²项的线性扫描，所以复杂度也是O(n²)。因此，这种方法的总体复杂度为 O(n² log(n))。