贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
🙋提问： 例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
回答：每一次都拿走当前钞票面值最大的那一张。最终就是拿走的是最大数额的钱。每一次拿走的最大就是局部最优，最终拿走的面值的总额就是全局最优。
题目
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
示例 1
输入: g = [1,2,3], s = [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。 虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。 所以你应该输出 1。
示例 2
输入: g = [1,2], s = [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出 2。
代码实现
/** * g - 小孩数组，数字代表胃口值 [1,2,3] 3 个孩子的胃口值分别是：1,2,3 * s - 饼干数组，数字代表尺寸 [1,2,3] 3块饼干，尺寸分别是 1,2,3 */function findContentChildren(g, s) { // 1. 先对小孩的胃口值还有饼干尺寸进行排序 g.sort((a, b) => a - b) // 对胃口值排序 s.sort((a, b) => a - b) // 对饼干尺寸进行排序
let count = 0 // 记录满足孩子的数量 let i = 0 // 孩子数组的指针 let j = 0 // 饼干数组的指针
// 同时遍历孩子和饼干的数组 while (i < g.length && j < s.length) { if (s[j] >= g[i]) { count++ i++ // 下一个孩子 j++ // 当前的饼干也被用了，移动到下一块饼干 } else { // 因为饼干是排好序了的，直接尝试下一块饼干 j++ } }
return count}【有一堆钞票，拿走十张，要达到最大金额】
function getMaxAmount(bills) { bills.sort((a, b) => b - a) // 从大到小排序
const selectedBills = bills.slice(0, 10)
const totalAmount = selectedBills.reduce((sum, bill) => sum + bill, 0)
return { selectedBills, totalAmount }}
// 一堆钞票const bills = [50, 100, 5, 20, 10, 200, 1000, 500, 50, 5, 10, 50, 100, 200, 500]const result = getMaxAmount(bills)console.log(result)-EOF-