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))。