# Greedy

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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):
itemsCarried=[]

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

foreach i in items:

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. Note that this solution is not optimal. For example, consider the set of weights 3, 2, 2 and respective values 3, 2, 2, with a knapsack of size 4. The preceding algorithm selects the single item with value 3, but an optimal solution selects the two items with value 2. There is no greedy algorithm for the 0-1 knapsack problem.

There is, however, a greedy algorithm that solves the continuous knapsack problem, in which the thief is not required to take the entire amount of a selected item. This algorithm sorts the items in order of decreasing value per unit weight, then takes as much as possible of each item in order.

def ContinuousKnapsack(items,MAX_LOAD):
empty the knapsack

sort(items)  #sort in descending order of item.value / item.weight

foreach i in items: