Greedy Algorithms

A place for implementation of greedy algorithms

Features

  • To see all the available functions in a module, you can just type help() with the module name as argument. For example,
>>> from pygorithm import greedy_algorithm
>>> help(greedy_algorithm)
    Help on package pygorithm.greedy_algorithm in pygorithm:

    NAME
    pygorithm.greedy_algorithm - Collection for greedy algorithms

    PACKAGE CONTENTS
    activity_selection
    fractional_knapsack

    DATA
    __all__ = ['fractional_knapsack', 'activity_selection']

Activity Selection Problem

  • Functions and their uses

Author: OMKAR PATHAK Created On: 26th August 2017

pygorithm.greedy_algorithm.activity_selection.activity_selection(start_times, finish_times)[source]

The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time.

Parameters:
  • start_times – An array that contains start time of all activities
  • finish_times – An array that conatins finish time of all activities
pygorithm.greedy_algorithm.activity_selection.get_code()[source]

returns the code for the activity_selection function

Fractional Knapsack

  • Functions and their uses

Author: SHARAD BHAT Created On: 22nd August 2017

pygorithm.greedy_algorithm.fractional_knapsack.knapsack(w, item_values, item_weights)[source]

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

Parameters:
  • w – maximum weight capacity
  • item_values – a list of values of items in the knapsack
  • item_weights – a list of weights of items in the knapsack
pygorithm.greedy_algorithm.fractional_knapsack.get_code()[source]

returns the code for the knapsack function