New answers tagged greedy-algorithms
1
Here is a simple reasoning that shows your greedy algorithm is correct. No mathematical induction is required.
Call an image critical if the greedy algorithm places a guard $0.5$ after it.
The algorithm ensures that each critical image is more than $1.5$ away from the previous critical image (except the first image, before which there is no image). That ...
0
Check e.g. Jeff Erickson's Algorithms (warning, somewhat though going), it has a thorough chapter on greedy algorithms. He also warns that greedy algorithms very rarely give optimal results (The underlying problem has to have a very particular structure for them to work in all cases, see e.g. Jeremy Kun's "When Greedy Algorithms are Perfect". Sure, ...
1
Usually, in the context of dynamic programming and optimization methods, we are interested in problems where we have to "find" some value which maximizes \ minimizes a certain function.
For example, take the following problem: You are a cashier in a shop, and a customer gave you an $n$-dollar bill (your country has bills of all kinds! very ...
2
Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.
To answer your question, let's look at a simple example, change-making problem:
Given a set of integer values of coins $C = \{c_1, …, ...
-2
if you are not able to prove and it's getting difficult then just find one test case that contradicts your greedy approach and you are good to go
Top 50 recent answers are included
