30 Days of Algorithms: From Zero to Intermediate (25/30) — Greedy algorithms
Greedy algorithms take a simple approach of making the locally optimal choice at each step, with the hope of finding the overall best solution.
Greedy algorithms may not always find the absolute best solution. Despite this, they are often efficient and effective for many problems. They can find very good solutions quickly, which is valuable in many cases.
Knapsack problem
We want a new iPhone, but we don’t have any money, so we decide to steal some items from the iStore. However, we don’t want to take the risk just for an iPhone; instead, we aim to steal as much as possible.
Upon arriving at the store, we realize we don’t have much time and need to act quickly. Therefore, we decide to steal only 2 kg of items.
Let’s round the weights.
The easiest solution is to steal the most expenesive stuff. Let's steal the monitor for 1599 usd. But clearly we missed something we had to steal iPhone + Macbook. This is where greedy algorithms fail. We will learn better approach with dynamic programming.
