algorithms.greedy

Covering segments

Given a set of n segments {[a(0) ,b(0) ],[a(1) ,b(1) ],…,[a(n)−1 ,b(n)−1 ]} with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point.

covering_segments(segments: [<class 'tuple'>]) → list

Function for finding minimum number of points that each segment contains

Parameters:segments – list of tuples with start and end point coordinates Returns:list of points where segments are crossing

Examples

>>> covering_segments([(4, 7), (1, 3), (2, 5), (5, 6)])
[3, 6]

Fractional Knapsack

Given weights and values of n items, we need put these items in a knapsack of capacity W to get the maximum total value in the knapsack.

Complexity: O(n log n)

fractional_knapsack(capacity: int, items: [<class 'tuple'>]) → float

Function solves fractional knapsack problem

Parameters:

• capacity – total capacity of backpack
• items – list of tuples [(value, weight),…]

Returns:

float - maximum value that can be placed in backpack

Examples

>>> fractional_knapsack(50, [(60, 10), (100, 20), (120, 30)])
240.0