优化PHP算法：寻找目标数的最优组合解法

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《优化PHP算法：寻找目标数的最优近似组合》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下，希望所有认真读完的童鞋们，都有实质性的提高。

本文介绍如何在PHP中从预设数值数组中高效地查找一个目标数的最佳构成要素。针对传统贪婪算法的不足，我们提出一种优化方法，通过遍历所有可能的构成数值，计算其倍数和余数，并利用自定义排序逻辑，优先选择余数最小、其次选择倍数最小的方案，从而实现更精确的近似匹配。

引言：理解数值构成问题

在许多业务场景中，我们可能需要从一组预设的数值（例如商品尺寸、货币面额、资源配额等）中，找出最接近或精确构成某个目标总量的组合。例如，给定一个目标金额3000，以及一组可选的数值：{700, 800, 900, 950, 1000, 1100, 1200, 1300}，我们需要找到一个或多个这些数值的组合，使其总和尽可能接近3000，且余数最小。如果存在多种方案余数相同，则通常倾向于选择使用较少构成次数的方案。

传统贪婪算法的局限性

一种常见的直观做法是采用贪婪策略：从最大的预设数值开始，尽可能多地使用它，然后用剩余的金额对下一个最大的数值重复此过程。然而，这种方法并非总能得到最优解。

考虑以下PHP代码示例，它展示了这种贪婪策略：

<?php
$amount = 3000;
$sizes = array(1300, 1200, 1100, 1000, 950, 900, 800, 700); // 注意这里已按降序排列

$result = array();
$remaining_amount = $amount; // 使用一个变量来跟踪剩余金额

foreach ($sizes as $size) {
    if ($remaining_amount >= $size) {
        $times = floor($remaining_amount / $size);
        $result[$size] = $times;
        $remaining_amount -= $times * $size;
    } else {
        $result[$size] = 0;
    }
}

echo '<pre>'; print_r($result); echo '

对于目标金额 3000，上述代码的输出将是：

Array
(
    [1300] => 2
    [1200] => 0
    [1100] => 0
    [1000] => 0
    // ... 其他为0
)

这表示使用了两个 1300，总计 2600，剩余 400。然而，我们知道 1000 * 3 = 3000 是一个更优的解决方案，它能精确构成目标金额，余数为 0。这说明贪婪算法在某些情况下会错过全局最优解。

优化方案：全面评估与智能排序

为了克服贪婪算法的局限性，我们需要一种方法来评估所有可能的“单个构成要素”方案，并从中选出最佳的一个。这里的“单个构成要素”指的是从预设数组中选取一个数值，并重复使用它来逼近目标金额。

步骤一：计算所有可能的构成方案

核心思想是遍历 sizes 数组中的每一个预设数值，独立地计算它能构成目标金额的次数 (times) 和此时产生的余数 (remainder)。

<?php
$amount = 3000;
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ]; // 顺序不影响此步骤

$evaluation_results = [];

foreach ($sizes as $size) {
  $times = (int)floor($amount / $size); // 计算当前size能构成的次数
  $remainder = $amount - $times * $size; // 计算余数

  $evaluation_results[] = [
      'size' => $size,
      'times' => $times,
      'remainder' => $remainder
  ];
}

// 此时 $evaluation_results 包含了所有单一种类构成方案的评估
// ... 接下来进行排序
?>

在这一步之后，$evaluation_results 数组将包含类似以下结构的数据：

Array
(
    [0] => Array ( [size] => 1300, [times] => 2, [remainder] => 400 )
    [1] => Array ( [size] => 1200, [times] => 2, [remainder] => 600 )
    [2] => Array ( [size] => 1100, [times] => 2, [remainder] => 800 )
    [3] => Array ( [size] => 1000, [times] => 3, [remainder] => 0 ) // 理想方案
    // ... 其他
)

步骤二：自定义排序以寻找最佳方案

为了找到“最佳”方案，我们需要对 evaluation_results 数组进行排序。排序的优先级规则如下：

1. 主要排序键：余数 (remainder)。我们希望余数尽可能小，因此按升序排列。余数为 0 的方案是最佳的。
2. 次要排序键：构成次数 (times)。如果两个方案的余数相同，我们倾向于选择使用次数较少的那一个（这通常意味着使用了更大的构成数值，或者在相同余数下更简洁的方案）。因此，按升序排列。

PHP的 usort 函数非常适合这种自定义排序需求。

<?php
// ... （接上一步的代码）

usort($evaluation_results, static function ($item1, $item2): int {
  // 首先比较余数，余数小的排在前面
  $comparison = $item1['remainder'] <=> $item2['remainder'];

  // 如果余数相同，则比较构成次数，次数少的排在前面
  return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});

echo '<pre>'; print_r($evaluation_results); echo '

示例代码与结果分析

将上述两个步骤整合，完整的PHP代码如下：

<?php
$amount = 3000; // 目标金额
$sizes = [ 1300, 1200, 1100, 1000, 950, 900, 800, 700 ]; // 预设构成数值

$evaluation_results = [];

// 步骤一：计算所有可能的构成方案
foreach ($sizes as $size) {
  $times = (int)floor($amount / $size);
  $remainder = $amount - $times * $size;

  $evaluation_results[] = [
      'size' => $size,
      'times' => $times,
      'remainder' => $remainder
  ];
}

// 步骤二：自定义排序以寻找最佳方案
usort($evaluation_results, static function ($item1, $item2): int {
  // 优先按余数升序排序
  $comparison = $item1['remainder'] <=> $item2['remainder'];
  // 如果余数相同，则按构成次数升序排序
  return $comparison === 0 ? $item1['times'] <=> $item2['times'] : $comparison;
});

echo '<pre>';
print_r($evaluation_results);
echo '

运行这段代码，输出将是：

Array
(
    [0] => Array
        (
            [size] => 1000
            [times] => 3
            [remainder] => 0   // 最佳结果：余数为0
        )

    [1] => Array
        (
            [size] => 950
            [times] => 3
            [remainder] => 150 // 次佳结果
        )

    [2] => Array
        (
            [size] => 700
            [times] => 4
            [remainder] => 200
        )

    [3] => Array
        (
            [size] => 900
            [times] => 3
            [remainder] => 300
        )

    [4] => Array
        (
            [size] => 1300
            [times] => 2
            [remainder] => 400
        )

    [5] => Array
        (
            [size] => 1200
            [times] => 2         // 余数与下一个相同，但次数更少，故排在前
            [remainder] => 600
        )

    [6] => Array
        (
            [size] => 800
            [times] => 3         // 余数与上一个相同，但次数更多，故排在后
            [remainder] => 600
        )

    [7] => Array
        (
            [size] => 1100
            [times] => 2
            [remainder] => 800
        )
)

通过这个排序后的数组，我们很容易就能找到最优解：数组的第一个元素 [0] 即是最佳方案。对于目标金额 3000，最佳方案是使用 1000 这个数值 3 次，余数为 0。

注意事项与进阶思考

1. 方案的适用范围：本教程提供的解决方案旨在找到一个“单一类型构成要素”的最佳近似，即从预设数组中选择一个 size，并重复使用它 times 次来逼近目标金额。它不会自动寻找由多个不同 size 组成的复杂组合（例如，为了构成 3500，使用 1200 + 1200 + 1100 这样的组合）。如果需要解决这类“多类型组合”问题，则需要采用更复杂的算法，如动态规划（背包问题变种）。
2. 性能考量：对于小型 sizes 数组（如本例中只有8个元素），此方法非常高效。其时间复杂度主要取决于 sizes 数组的长度 N (遍历操作) 和排序操作 (N log N)，总体性能良好。
3. 应用场景：此方法适用于需要从一组固定规格中选择最佳单一规格来满足需求的场景，例如：
   • 库存分配：从不同容量的包装中选择一种来尽可能装满某个体积。
   • 资源规划：从不同规格的设备中选择一种来满足特定计算需求。
   • 货币找零（简化版）：假设只能用一种面额的硬币找零，如何最接近目标金额。

总结

通过对所有可能的单一构成方案进行全面评估，并结合自定义排序逻辑，我们可以有效地从一组预设数值中找到一个目标数的最佳近似构成。这种方法避免了贪婪算法可能导致的局部最优问题，确保了在给定约束下的最优解。在实际开发中，理解问题的具体需求（是寻找单一构成还是多重组合）是选择合适算法的关键。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《优化PHP算法：寻找目标数的最优组合解法》文章吧，也可关注golang学习网公众号了解相关技术文章。