我通过逐步优化贪心算法使其性能达到88%+59
发布时间
阅读量：
阅读量
一、题目描述
分发饼干
假如你是位优秀的家长，在为你的孩子分发小饼干。然而，请注意：每个孩子最多只能获得一块饼干。
对于每个孩子i来说，有一个最小满足其胃口所需的饼干尺寸g[i]；而每块饼干j的尺寸是s[j]。
当饼干j的尺寸s[j]大于或等于孩子的胃口g[i]时（即s[j]>=g[i]），我们可以将此饼干分配给孩子i，并使该孩子得到满足。
你的目标是在尽可能多地满足孩子的前提下输出最大数量的孩子数目。
为了达到这一目的，请考虑以下算法思路：
首先将所有孩子的胃口值数组进行排序；
接着将所有可分配的饼干尺寸数组也进行排序；
然后使用贪心算法策略：从最小的孩子开始尝试分配最小可用的符合要求的饼干；
最终统计并输出成功配对的数量。
二、思路分析
熟悉笔者之前分享过多篇关于动态规划算法的知识，在此题中如果采用动态规划方法解决会遇到一个主要难点--二维问题。
那么"二维"具体指的是什么呢？
在之前的讨论中我们知道，在动态规划中机器人寻址问题同样属于二维问题。
那么为何能够采用动态规划方法来解决这个问题呢？
首先我们回顾一下机器人行走的过程，在这种情况下我们的当前状态(i,j)与其上面两种可能的状态存在关联关系，并且这种关联关系可以通过方程进行描述。
全部评论 (0)
还没有任何评论哟~