PHP实现的贪婪算法实例

算法简介

贪心算法是一种普遍的算法思想，它在很多经典的问题上都有着出色的表现。该算法贪心地选择局部最优解，并且希望最终得到全局最优解。

算法应用

贪心算法通常应用于信息完全的情况下，出现不可预知情况时就需要用到其他算法。例如，Kruskal最小生成树算法就是一种基于贪心策略的算法。

算法示例

示例1：找零钱问题

假设某次消费了 $77 元，现有面值为 $1、$5、$10、$20、$50 和 $100 元的人民币若干张。请问如何找零才能保证所扣余额最小？

我们可以使用贪心算法：从面值最大的纸币开始，尽可能多地选取，直到选取的纸币面值总和超过需找的零钱金额。然后退回到面值次大的纸币，继续进行前述操作，直到找出所有需要的纸币。

下面是 PHP 实现代码：

function make_change($money, $coins) {
    arsort($coins);
    $change = array();
    foreach($coins as $value){
        $needed = intval($money / $value);
        $money -= $needed * $value;
        $change[$value] = $needed;
    }
    return $change;
}

在下面的示例中，我们使用了上述代码来计算需要找的零钱，前提条件是有足够的纸币可以用于找钱：

$money = 77;
$coins = array(100, 50, 20, 10, 5, 1);
$res = make_change($money,$coins);
print_r($res);

运行结果：

Array
(
    [100] => 0
    [50] => 1
    [20] => 1
    [10] => 0
    [5] => 1
    [1] => 2
)

该函数返回了一个数组，其中键代表每种找回的纸币面值，值代表所需的纸币数量。

示例2：区间计算问题

假设有一组区间，需要选择尽量多的区间，使得它们的交集非空。例如，区间集合为 $[[1,3], [2,4], [3,5], [4,6], [5,7]]$，则选取 $[2,4],[4,6]$，并且这是最优解。

我们可以使用贪心算法：首先将所有区间按照结束时间升序排序，然后从第一个区间开始，选取结束时间最早的区间，然后选取最早结束的对于后面的区间来说是最优解，直到所有区间都被覆盖。

下面是 PHP 实现代码：

function interval_covering($intervals) {
    usort($intervals, function($a, $b) {
        return $a[1] > $b[1];
    });
    $last_cover = PHP_INT_MIN;
    $selected_intervals = array();
    foreach ($intervals as $interval) {
        $start = $interval[0];
        $end = $interval[1];
        if($start < $last_cover) 
            continue;
        array_push($selected_intervals, $interval);
        $last_cover = $end;
    }
    return $selected_intervals;
}

在下面的示例中，我们使用上述代码来计算所需选取的区间：

$intervals = array(
    array(1,3),
    array(2,4),
    array(3,5),
    array(4,6),
    array(5,7)
);
$res = interval_covering($intervals);
print_r($res);

运行结果：

Array
(
    [0] => Array
        (
            [0] => 2
            [1] => 4
        )

    [1] => Array
        (
            [0] => 4
            [1] => 6
        )

)