贪心算法求解免费馅饼问题

免费馅饼问题可以使用贪心算法求解。

免费馅饼问题描述如下：有一个人在走迷宫，并且路上有一些馅饼。每个馅饼都有一定的重量和价值。这个人背包最多只能装下一定的重量，现在需要选择哪些馅饼放入背包，使得背包中的馅饼总价值最大。

假设背包容量为W，馅饼数量为N，每个馅饼的重量为w[i]，价值为v[i]。

贪心算法的基本思路是每次选择当前最优解，即选择当前重量最轻且价值最高的馅饼。具体实现可以按照以下步骤进行：

1. 将馅饼按照单位重量的价值从大到小排序。
2. 依次将馅饼加入背包，直到背包的容量达到W 或者所有的馅饼都已经加入背包。

贪心算法的正确性可以通过反证法证明。假设存在一种非贪心的算法A得到的解比贪心算法B得到的解更优，则必然存在一种馅饼i，使得算法A没有选择该馅饼而算法B选择了该馅饼。因为算法B是贪心算法，所以该馅饼i必然是剩余馅饼中单位重量的价值最大的馅饼。如果算法A选择了该馅饼，则算法A的解和算法B的解是一样的，矛盾。如果算法A没有选择该馅饼，则算法A的解比算法B的解更劣，矛盾。

因此，使用贪心算法可以得到免费馅饼问题的最优解。