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
)
)
总结
贪心算法作为一种常用的算法思想,可以在很多领域得到应用,其优点是较为简单,但缺点是不能保证得到全局最优解,因此在适用的场景下需要慎重使用。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:PHP实现的贪婪算法实例 - Python技术站