Greedy implementation of Fractional Knapsack

fractional_knapsack.py

items = [(20, 4), (18, 3), (14, 2)]
W = 7

def fractional_knapsack_naive(items, bag_weight):
    """
    Maximize the value of items that fit into knapsack
    constrained to bag_weight

    Args:
    items: list of tuples containing (value_i, weight_i) pairs
    bag_weight: knapsack weight

    Returns:
    maximum value knapsack can carry

    Running time: O(mn)
    m: bag weight
    n: number of items
    """
    cost = 0
    while bag_weight > 0:
        max_density_idx, max_density = 0, 0
        for index in range(len(items)):
            if items[index][1] > 0:
                density = items[index][0] / items[index][1]
                if density > max_density:
                    max_density, max_density_idx = density, index
        alpha = min(items[max_density_idx][1], bag_weight)
        cost += alpha * max_density
        bag_weight -= alpha
        items[max_density_idx] = (
            items[max_density_idx][0],
            items[max_density_idx][1] - alpha,
        )
    return cost


def fractional_knapsack(items, bag_weight):
    """
    Maximize the value of items that fit into knapsack
    constrained to bag_weight

    Args:
    items: list of tuples containing (value_i, weight_i) pairs
    bag_weight: knapsack weight

    Returns:
    maximum value knapsack can carry

    Running time: O(nlogn)
    """
    taken = [0] * len(items)
    max_value = 0
    sorted_items = sorted(items, key=lambda item: item[0] / item[1], reverse=True)[::]
    value_idx, weight_idx = 0, 1
    for (idx, item) in enumerate(sorted_items):
        if bag_weight == 0:
            return (max_value, taken)
        number_of_items_to_take = min(item[weight_idx], bag_weight)
        max_value += number_of_items_to_take * item[value_idx] / item[weight_idx]
        sorted_items[idx] = (
            item[value_idx],
            item[weight_idx] - number_of_items_to_take,
        )
        bag_weight -= number_of_items_to_take
        taken[idx] = number_of_items_to_take
    return taken, max_value


fractional_knapsack(items, W)