贪心算法及其实现 [英] The greedy algorithm and implementation

问题描述

你好，我刚刚开始学习贪婪算法，并且我首先研究了经典的找零问题。我可以理解算法中的贪婪（即选择局部最优解朝向全局最优。），因为我选择的是硬币的最高价值，使得
sum + {value的硬币}}< =总价值。然后，我开始在某些站点中解决一些贪婪算法问题。我可以解决大多数问题，但无法确切地指出贪婪在问题中的应用位置。我编写了我能想到的唯一解决方案，以解决问题并得到了接受。社论也显示了解决问题的相同方法，但我无法理解贪婪范式在算法中的应用。

Hello I've just started learning greedy algorithm and I've first looked at the classic coin changing problem. I could understand the greediness (i.e., choosing locally optimal solution towards a global optimum.) in the algorithm as I am choosing the highest value of coin such that the sum+{value of chosen coin}<=total value . Then I started to solve some greedy algorithm problem in some sites. I could solve most of the problems but couldn't figure out exactly where the greediness is applied in the problem. I coded the only solution i could think of, for the problems and got it accepted. The editorials also show the same way of solving problem but i could not understand the application of greedy paradigm in the algorithm.

贪婪算法是解决特定范围的唯一方法问题？还是它们是解决可能更有效的问题的一种方法？

Are greedy algorithms the only way of solving a particular range of problems? Or they are one way of solving problems which could be more efficient?

您是否可以在没有使用贪婪范式的情况下给我同样问题的伪代码？

Could you give me pseudo codes of a same problem with and without the application of greedy paradigm?

推荐答案

贪婪算法有很多现实的例子。一个明显的问题是硬币兑换问题，要兑换某种货币，我们要反复分配最大的面额，因此，要出十七美元和六十一美分的零钱，我们要出十美元的钞票，五美元-美元的钞票，两张一美元的钞票，两个季度，一角钱和一分钱。通过这样做，我们保证将纸币和硬币的数量减至最少。此算法不适用于所有货币系统... 更多此处

There are lots of real life examples of greedy algorithms. One of the obvious is the coin changing problem, to make change in a certain currency, we repeatedly dispense the largest denomination, thus , to give out seventeen dollars and sixty one cents in change, we give out a ten-dollar bill, a five-dollar bill, two one-dollar bills, two quarters , one dime, and one penny. By doing this, we are guaranteed to minimize the number of bills and coins. This algorithm does not work in all monetary systems...more here

这篇关于贪心算法及其实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！