greed algorithm in python

Greedy algorithm is a problem-solving approach where the solution is built incrementally based on making the locally optimal choice at each step. Here's an example implementation of the greedy algorithm in Python:

main.py
def knapsack(capacity, items):
    """
    Given a list of items (value, weight) and a capacity, return the maximum value 
    that can be obtained by selecting items such that the sum of their weights is less than or equal to capacity. 
    """
    total_value = 0
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True) # sort by value/weight ratio

    for value, weight in items:
        if capacity == 0:
            return total_value
        elif weight <= capacity:
            total_value += value
            capacity -= weight
        else:
            fraction = capacity/weight
            total_value += value*fraction
            capacity -= weight*fraction
            break

    return total_value
724 chars
22 lines

This implementation solves the fractional knapsack problem where the items can be divided into smaller parts. The function takes two arguments - the knapsack capacity and a list of items in the form of (value, weight) tuples. The algorithm sorts the items based on their value-to-weight ratio in descending order and selects the items with the highest ratio until the knapsack capacity is reached. If an item cannot fit into the remaining capacity, it is partially added to the knapsack in proportion to its weight. The function returns the total value of the selected items.