我如何回答这个贪心算法问题？

Question

我正在学习贪婪算法及其应用。下面的问题是老师提供的许多帮助学习贪婪算法的问题中的第一个。

Q）您正在保育n个孩子，并且有m个> n个cookie在它们之间划分。你必须给每个孩子只有一个Cookie（当然，您不能将同一个Cookie分配给两个不同的Cookie儿童）。每个孩子的贪婪因子gi为1≤i≤n，这是cookie的最小大小，孩子会很高兴；每个cookie的大小为sj，1≤j≤m。您的目标是最大限度地提高快乐儿童的数量，即为我分配了gi≤sj的cookie j。为此问题提供正确的贪婪算法

如果有人可以帮助我解决这个问题，我将非常感激。还有更多类似的内容，但是我想如果我能做到这一点，我将能够做到。

谢谢！

Answer 1

您已经在注释中正确识别了算法：

我们必须尽可能以升序分配cookie为它分配最不贪婪的孩子

您可以像这样将算法分解为简单的步骤

Sort the children ascending by greed factor 
For each child in the sorted list
    if there is at least one cookie remaining that will make the child happy
        give the child the smallest cookie that will make the child happy