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
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