Greedy

From Algorithmist

Greedy algorithms are one set of algorithms designed to solve optimization problems. They function by calculating the locally optimal solution at every iteration in the hope that this local solution will be part of the optimal global solution. For example, a very simple solution to the 0-1 Knapsack Problem.

def ZeroOneKnapsack(items,MAX_LOAD):
    loadCarried=0
    itemsCarried=[]

    sort(items)     #sort the items in descending order of value

    foreach i in items:
        if(loadCarried i.weight<=MAX_LOAD):
            itemsCarried.add(i)
            loadCarried =i.weight

    return itemsCarried


class item:
    public value
    public weight

At every iteration the object of highest value is chosen, until there are either no more items or the knapsack is full.

One of the largest downfalls of greedy algorithms is that they do not always produce optimal results. They benefit from being relatively simple to write, and often provide a close approximation to an optimal solution.