# 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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions