What
is “Greedy algorithm”? Write its pseudo code.
Ans
A
greedy algorithm is a mathematical process that recursively constructs a set of
objects from the smallest possible constituent parts. Recursion is an approach
to problem solving in which the solution to a particular problem depends on
solutions to smaller instances of the same problem.
Greedy
algorithms look for simple, easy-to-implement solutions to complex, multi-step
problems by deciding which next step will provide the most obvious benefit.
Such algorithms are called greedy because while the optimal solution to each
smaller instance will provide an immediate output, the algorithm doesn’t
consider the larger problem as a whole. Once a decision has been made, it is
never reconsidered.
The
advantage to using a greedy algorithm is that solutions to smaller instances of
the problem can be straightforward and easy to understand. The disadvantage is
that it is entirely possible that the most optimal short-term solutions may
lead to the worst long-term outcome.
Greedy
algorithms are often used in ad hoc mobile networking to efficiently route
packets with the fewest number of hops and the shortest delay possible. They
are also used in machine learning, business intelligence (BI), artificial
intelligence (AI) and programming.
I
am trying to write the pseudocode for an algorithm that gives change (so that
the least number of coins are used) for a total value (using a wide variety of
coin systems).
I am using the British system: {1,2,5,10,20,50, 100}|
1 Let change be an empty set
|
|
2
|
for i = 1,
... , r
|
|
3
|
do while n
>= ci
|
|
4
|
do C
= C and ci
|
|
5
|
do n
= n - ci
|
|
6
|
return C
|
I
have attempted it below, but it doesn't seem like it is going in the right
direction...
Input:
An integer n and a set of coin denominations c1; c2; .... ; cr with
c1<c2...<cr
Output:
A set of coins d1;d2;...;dk such that the summation of di (from i = 1 to k) = n
and k is minimised.
No comments:
Post a Comment