本文介绍一种基于 mysql 窗口函数与 laravel eloquent 结合的方案，用于从用户表中选出每个需求类别（如 clown、host）各一人，使其 talent fee 总和最接近但不超过客户预算的最优组合。
本文介绍一种基于 mysql 窗口函数与 laravel eloquent 结合的方案，用于从用户表中选出每个需求类别（如 clown、host）各一人，使其 talent fee 总和最接近但不超过客户预算的最优组合。
在活动策划类应用中，常见需求是：客户指定所需角色（如 Clown、Host、Organizer）及总预算，系统需从候选人中为每个角色精确匹配一人，使三人总费用 ≤ 预算，且尽可能接近该预算（即“最接近可行解”）。这本质上是一个带约束的子集和优化问题（受限于类别唯一性），无法通过简单聚合或 WHERE 条件直接解决，需借助数据库层的排序、分组与累积计算能力。
✅ 核心思路：按类别取最低费用者 → 构建可行解空间 → 优选最接近预算的组合
由于 MySQL 不支持跨行回溯式组合枚举（如全排列），我们采用启发式贪心策略：对每个类别，优先选取费用最低的候选人（保障可行性），再通过 Laravel 层逻辑扩展为多候选组合（如每类取 Top-3），最后在 PHP 中筛选总和最优的合法组合。此法兼顾性能与准确性，适用于中小规模数据（单类 ≤ 100 人）。
? 步骤 1：按类别预取低成本候选人（MySQL + Eloquent）
// 假设 $needs = ['Clown', 'Host', 'Organizer'], $budget = 3200
$needs = $request->input('needs', ['Clown', 'Host', 'Organizer']);
$budget = (int) $request->input('budget', 3200);
// 每个类别取费用最低的 3 人（平衡精度与性能）
$candidatesByCategory = [];
foreach ($needs as $category) {
$candidatesByCategory[$category] = User::where('category', $category)
->orderBy('talent_fee', 'asc')
->take(3)
->get(['id', 'name', 'category', 'talent_fee']);
}
? 步骤 2：生成所有合法组合并筛选最优解（PHP 层）
use Illuminate\Support\Collection;
// 生成笛卡尔积：每个类别选 1 人 → 所有可能组合
$combinations = collect([$candidatesByCategory])->reduce(function ($carry, $group) {
if ($carry->isEmpty()) return $group->map(fn($v) => [$v]);
return $carry->flatMap(function ($prefix) use ($group) {
return $group->map(function ($item) use ($prefix) {
return array_merge($prefix, [$item]);
});
});
}, collect([]));
// 过滤：总费用 ≤ 预算，且类别不重复（本例已保证）
$validCombinations = $combinations->filter(function ($combo) use ($budget) {
return $combo->sum('talent_fee') values();
// 按总费用降序，取最接近预算的组合（即最大可行和）
$bestCombo = $validCombinations->sortByDesc(function ($combo) {
return $combo->sum('talent_fee');
})->first();
if ($bestCombo) {
$selectedUsers = $bestCombo->map(fn($u) => [
'id' => $u->id,
'name' => $u->name,
'category' => $u->category,
'talent_fee' => $u->talent_fee
])->values();
// 返回：John (900), Cris (800), Joe (1500) → Sum = 3200 ✅
return response()->json([
'users' => $selectedUsers,
'total_fee' => $selectedUsers->sum('talent_fee'),
'remaining_budget' => $budget - $selectedUsers->sum('talent_fee')
]);
} else {
return response()->json(['message' => 'No valid combination found within budget.'], 404);
}
⚠️ 注意事项与优化建议
- 性能边界：若每类取 N 人，k 类则生成 N^k 种组合。建议 N ≤ 3，k ≤ 5；超限时应改用数据库 CTE 递归或专用算法库（如 knapsack-php）。
- 数据库替代方案（MySQL 8.0+）：可借助窗口函数 + 自连接模拟有限组合，但复杂度高、可维护性差，不推荐作为首选。
- 严格最优解？ 本方案是近似最优（贪心+局部搜索）。如需全局最优，需引入整数规划（如 CBC Solver）或限制类别数后暴力枚举。
- Laravel 兼容性：代码兼容 Laravel 9+，使用原生 Collection 方法，无需额外包。
该方案以清晰的逻辑分层（DB 预筛选 → PHP 组合评估）实现了业务目标，在可维护性、性能与准确性间取得良好平衡。
