Home » Python

Optimization using Greedy Algorithm in Python

Python | Optimization using Greedy Algorithm: Here, we are going to learn the optimization with greedy algorithm in Python.
Submitted by Anuj Singh, on May 05, 2020

In the real world, choosing the best option is an optimization problem and as a result, we have the best solution with us. In mathematics, optimization is a very broad topic which aims to find the best fit for the data/problem. Such optimization problems can be solved using the Greedy Algorithm ("A greedy algorithm is an algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum"). This is the Wikipedia definition and we find one of the optimum solutions by keeping constraints in mind. This is one of the simplest algorithms used for optimization.

Let us consider a problem where Hareus gets 1500$ as pocket money. He is a hostler and needs to buy essentials for the month. So, he reserves 1000$ for essentials and now he has the rest of the 500$ for his spending. He went to the supermarket and there he had to decide what to buy according to the value(a measure of each item related to productivity) and also have a constraint of 500$. This is one of the optimization problems and the following is the code for choosing the items in one of the best ways.

Key Idea: Productivity Maximum with 500$.

Python Implementation:

# Greedy Algorithm for a Optimisation Problem

# Defined a class for item, 
# with its name, value and cost
class Itm(object):
    def __init__(self, name, val, cost):
        self.name = name
        self.val = val
        self.cost = cost
        
    def getvalue(self):
        return self.val
    
    def getcost(self):
        return self.cost
    
    def __str__(self):
        return self.name 
  
# Defining a function for building a List 
# which generates list of items that are 
# available at supermart   
def buildlist(names, values, costs):
    menu = []
    for i in range(len(names)):
        menu.append(Itm(names[i], values[i], costs[i]))
    return menu

# Implementation of greedy algorithm 
# to choose one of the optimum choice
def greedy(items, maxcal, keyfunction):
    itemscopy = sorted(items, key = keyfunction, reverse = True)
    
    result = []
    totalval = 0 
    totalcal = 0
    
    for i in range(len(items)):
        if (totalcal + itemscopy[i].getcost() <= maxcal):
            result.append(itemscopy[i])
            totalval = totalval + itemscopy[i].getvalue()
            totalcal = totalcal + itemscopy[i].getcost()
            
    return (result, totalval)


# Main Function
# All values are random    
names = ['Ball', 'Gloves', 'Notebook', 'Bagpack', 'Charger', 'Pillow', 'Cakes', 'Pencil']
values = [89,90,95,100,90,79,50,10]
costs = [123,154,25,145,365,150,95,195]
Itemrs = buildlist(names, values, costs)
maxcost = 500 # maximum money he have to spend

taken, totvalue = greedy(Itemrs, maxcost, Itm.getvalue)

print('Total vaule taken : ', totvalue)

# Printing the list of item slected for optimum value
for i in range(len(taken)):
    print('  ', taken[i])

Output

Total vaule taken :  374
   Bagpack
   Notebook
   Gloves
   Ball