According to Wikipedia, a greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding the global optimum. In general, greedy algorithms are used for optimization problems.
An example of a Greedy algorithm is a charging machine. Assume that it give you your change with € currency, you will have coin of : 200, 100, 50, 20, 10, 5, 2, 1. Your change will be really easy to calculate with a greedy algorithm :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| var moneySystem:Array = [200, 100, 50, 20, 10, 5, 2, 1];
var giveBack:uint = 263;
var solution:Array = [];
trace(greedyMethod(moneySystem, giveBack, solution));
function greedyMethod($moneySystem:Array, $giveBack:uint, $solution:Array):Array {
if ($giveBack == 0) {
return $solution;
}
while ($giveBack >= $moneySystem[0]) {
$giveBack -= $moneySystem[0];
$solution.push($moneySystem[0]);
}
$moneySystem.shift();
return greedyMethod($moneySystem, $giveBack, $solution);
} |
var moneySystem:Array = [200, 100, 50, 20, 10, 5, 2, 1];
var giveBack:uint = 263;
var solution:Array = [];
trace(greedyMethod(moneySystem, giveBack, solution));
function greedyMethod($moneySystem:Array, $giveBack:uint, $solution:Array):Array {
if ($giveBack == 0) {
return $solution;
}
while ($giveBack >= $moneySystem[0]) {
$giveBack -= $moneySystem[0];
$solution.push($moneySystem[0]);
}
$moneySystem.shift();
return greedyMethod($moneySystem, $giveBack, $solution);
}
For 263, the algorithm will output : 200,50,10,2,1. It is the best solution. Thanks to the € currency, greedy algorithm will always give the best results.
However if we have an other money with only 4, 3, 1 coins and the change is 6 the greedy algorithm outputs 4, 1, 1 instead of 3, 3. That’s a fail !
Another typical example is the knapsack problem : given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
According that our values are sorted in decreasing order we have :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| var objects:Array = [["A", 12, 10], ["B", 10, 7], ["C", 8, 5], ["D", 7, 4],
["E", 7, 4], ["F", 6, 4], ["G", 5, 2], ["H", 4, 2],
["I", 4, 1], ["J", 3, 2], ["K", 3, 2], ["L", 3, 1],
["M", 2, 2], ["N", 1, 1]];
var totalWeight:uint = 25;
trace(knapSack(totalWeight, objects));
function knapSack($totalWeight:uint, $objects:Array):Array {
var currentWeight:uint = 0;
var subSet:Array = [];
for (var counter:uint;counter< $objects.length; ++counter) {
if (currentWeight + $objects[counter][2] <= $totalWeight) {
currentWeight += $objects[counter][2];
subSet.push($objects[counter]);
}
}
return subSet;
} |
var objects:Array = [["A", 12, 10], ["B", 10, 7], ["C", 8, 5], ["D", 7, 4],
["E", 7, 4], ["F", 6, 4], ["G", 5, 2], ["H", 4, 2],
["I", 4, 1], ["J", 3, 2], ["K", 3, 2], ["L", 3, 1],
["M", 2, 2], ["N", 1, 1]];
var totalWeight:uint = 25;
trace(knapSack(totalWeight, objects));
function knapSack($totalWeight:uint, $objects:Array):Array {
var currentWeight:uint = 0;
var subSet:Array = [];
for (var counter:uint;counter< $objects.length; ++counter) {
if (currentWeight + $objects[counter][2] <= $totalWeight) {
currentWeight += $objects[counter][2];
subSet.push($objects[counter]);
}
}
return subSet;
}
The output is [A,12,10],[B,10,7],[C,8,5],[G,5,2],[I,4,1]. It’s ok, but we aren’t sure that it is the best result. The problem with a greedy algorith : it will always try to select the first parameter even if it is not the better.
For instance, our max weight is 40, our objects are [“A”, 30, 39], [“B”, 12, 10], [“C”, 12, 10], [“D”, 12, 10], [“E”, 12, 10],[“F”, 4, 1]. The greedy algorithm choose A and F for a value of 34 whereas B, C, D, E is obviously the best value : 48. That’s an other example where it fails.
So to conclude greedy algorithms depends of datas if they are balanced or not. More data are balanced, more it will be powerful. For a perfect result, you can use dynamic programming method. It is more complex and requires more resources. So it’s up to us to find the best solution for our problem.