贪心算法是一种在每一步选择中都采取当前状态下最优决策的算法思想，它不会考虑整体最优性，仅关注当前步骤的最优选择，最终通过局部最优的累积得到全局结果。在PHP开发中，很多业务场景都可以通过贪心算法高效解决问题，下面先介绍典型的应用场景及实现方法。
贪心算法的适用前提
贪心算法并不是所有问题都适用，需要满足两个核心条件：一是贪心选择性质，即全局最优解可以通过一系列局部最优的选择得到；二是最优子结构性质，即问题的最优解包含其子问题的最优解。如果问题不满足这两个条件，使用贪心算法可能得到错误的结果。
场景一：零钱兑换问题
零钱兑换是贪心算法的经典应用场景，假设我们有面额为1元、5元、10元、20元、50元、100元的纸币，现在需要兑换出指定金额的零钱，要求使用的纸币数量最少，此时每次选择面额最大的纸币就是当前的最优选择。
PHP实现代码如下：
<?php
/**
* 贪心算法实现零钱兑换
* @param int $amount 需要兑换的总金额
* @param array $denominations 纸币面额数组，默认从大到小排序
* @return array 兑换结果，包含每种面额的数量
*/
function greedyChange($amount, $denominations = [100, 50, 20, 10, 5, 1]) {
$result = [];
// 遍历面额数组，每次选择当前最大面额
foreach ($denominations as $den) {
if ($amount >= $den) {
$count = intval($amount / $den);
$result[$den] = $count;
$amount -= $count * $den;
}
// 金额已经兑换完毕，跳出循环
if ($amount == 0) {
break;
}
}
return $result;
}
// 测试：兑换37元
$changeResult = greedyChange(37);
print_r($changeResult);
// 输出结果：Array ( [20] => 1 [10] => 1 [5] => 1 [1] => 2 )
?>
场景二：活动选择问题
活动选择问题是指有若干个活动，每个活动有开始时间和结束时间，需要在同一场地安排尽可能多的活动，且活动之间不能时间冲突。贪心策略是每次选择结束时间最早的活动，这样能为后续活动留出更多时间。
PHP实现代码如下：
<?php
/**
* 贪心算法实现活动选择
* @param array $activities 活动数组，每个元素包含start和end键
* @return array 选中的活动列表
*/
function greedyActivitySelect($activities) {
// 先按照活动结束时间升序排序
usort($activities, function($a, $b) {
return $a['end'] <=> $b['end'];
});
$selected = [];
$lastEndTime = 0;
foreach ($activities as $activity) {
// 如果当前活动开始时间大于等于上一个选中活动的结束时间，就选中该活动
if ($activity['start'] >= $lastEndTime) {
$selected[] = $activity;
$lastEndTime = $activity['end'];
}
}
return $selected;
}
// 测试活动数据，每个活动包含名称和起止时间
$activityList = [
['name' => '活动1', 'start' => 1, 'end' => 4],
['name' => '活动2', 'start' => 3, 'end' => 5],
['name' => '活动3', 'start' => 0, 'end' => 6],
['name' => '活动4', 'start' => 5, 'end' => 7],
['name' => '活动5', 'start' => 3, 'end' => 8],
['name' => '活动6', 'start' => 5, 'end' => 9],
['name' => '活动7', 'start' => 6, 'end' => 10],
['name' => '活动8', 'start' => 8, 'end' => 11],
];
$selectedActivities = greedyActivitySelect($activityList);
foreach ($selectedActivities as $act) {
echo $act['name'] . " 开始时间：" . $act['start'] . " 结束时间：" . $act['end'] . "<br/>";
}
// 输出结果：活动1 开始时间：1 结束时间：4；活动4 开始时间：5 结束时间：7；活动8 开始时间：8 结束时间：11
?>
场景三：部分背包问题
部分背包问题是指有若干物品，每个物品有重量和价值，背包有最大承重限制，物品可以分割，要求装入背包的物品总价值最大。贪心策略是每次选择单位重量价值最高的物品装入背包。
PHP实现代码如下：
<?php
/**
* 贪心算法实现部分背包问题
* @param array $items 物品数组，每个元素包含weight和value键
* @param int $capacity 背包最大承重
* @return float 装入背包的最大总价值
*/
function greedyKnapsack($items, $capacity) {
// 计算每个物品的单位重量价值，并添加到数组
foreach ($items as &$item) {
$item['unit_value'] = $item['value'] / $item['weight'];
}
// 按照单位重量价值降序排序
usort($items, function($a, $b) {
return $b['unit_value'] <=> $a['unit_value'];
});
$totalValue = 0.0;
$remaining = $capacity;
foreach ($items as $item) {
if ($remaining <= 0) {
break;
}
// 如果当前物品重量小于等于剩余承重，全部装入
if ($item['weight'] <= $remaining) {
$totalValue += $item['value'];
$remaining -= $item['weight'];
} else {
// 否则装入部分物品
$totalValue += $item['unit_value'] * $remaining;
$remaining = 0;
}
}
return $totalValue;
}
// 测试数据：三个物品，重量和价值分别为(10,60)、(20,100)、(30,120)，背包承重50
$itemList = [
['weight' => 10, 'value' => 60],
['weight' => 20, 'value' => 100],
['weight' => 30, 'value' => 120],
];
$maxValue = greedyKnapsack($itemList, 50);
echo "背包能装入的最大总价值为：" . $maxValue;
// 输出结果：背包能装入的最大总价值为：240
?>
贪心算法的局限性
虽然贪心算法实现简单、效率较高，但存在局限性，比如零钱兑换场景如果纸币面额不是标准面额，比如有面额1、3、4元的纸币，要兑换6元，贪心算法会先选4元，剩下2元选两个1元，总共3张纸币，而最优解是选两个3元，只需要2张纸币。因此在使用贪心算法前，需要先验证问题是否满足贪心选择性质和最优子结构性质，避免得到错误结果。