An algorithm design method that builds a solution by repeatedly picking the choice that looks best at that moment, without revisiting earlier choices. It is fast and simple, but it gives an optimal solution only when the problem has special properties, as with coin systems like Japan's or Kruskal's algorithm for minimum spanning trees.
Japanese name: 貪欲法
Greedy algorithm appears in 2 practice questions across 1 topic, including Data Structures and Algorithms.
Answer: B. The greedy algorithm uses 3 coins and misses the minimum of 2
The greedy algorithm first takes one 6-yen coin and pays the remaining 2 yen with two 1-yen coins, for 3 coins. But two 4-yen coins pay it with just 2. Because a greedy algorithm only accumulates the choice that looks best at each moment, it is not optimal for some coin systems. Dynamic programming, which fills in a table of the minimum number of coins for every amount from 0 to 8 yen in increasing order, always finds the minimum. For coin systems such as Japan's 1, 5, 10, 50, 100 and 500 yen, the greedy algorithm always gives the minimum.
The greedy algorithm first takes one 6-yen coin and pays the remaining 2 yen with two 1-yen coins, for 3 coins.
You pay 8 yen with coins of 1 yen, 4 yen and 6 yen. Which c…A greedy algorithm that packs items in order of value per unit weight takes the items of weight 2 and 3 (value 7), and then no item fits in the remaining capacity of 3, so it stops at 7.
A knapsack with capacity 8 is filled with items chosen from…As an Amazon Associate I earn from qualifying purchases.
Dynamic programming Binary heap Binary search Binary search tree Breadth-first search Depth-first search Dijkstra's algorithm Hash table Linked list Queue