https en wikipedia orgwikisetcoverproblem return the valuetoweight ratio for the item returns float the valuetoweight ratio for the item examples item10 65 ratio 6 5 item20 100 ratio 5 0 item30 120 ratio 4 0 solve the fractional cover problem args items a list of items where each item has weight and value attributes capacity the maximum weight capacity of the knapsack returns the maximum value that can be obtained by selecting fractions of items to cover the knapsack s capacity raises valueerror if capacity is negative examples fractionalcoveritem10 60 item20 100 item30 120 capacity50 240 0 fractionalcoveritem20 100 item30 120 item10 60 capacity25 135 0 fractionalcoveritem10 60 item20 100 item30 120 capacity60 280 0 fractionalcoveritemsitem5 30 item10 60 item15 90 capacity30 180 0 fractionalcoveritems capacity50 0 0 fractionalcoveritemsitem10 60 capacity5 30 0 fractionalcoveritemsitem10 60 capacity1 6 0 fractionalcoveritemsitem10 60 capacity0 0 0 fractionalcoveritemsitem10 60 capacity1 traceback most recent call last valueerror capacity cannot be negative sort the items by their valuetoweight ratio in descending order https en wikipedia org wiki set_cover_problem return the value to weight ratio for the item returns float the value to weight ratio for the item examples item 10 65 ratio 6 5 item 20 100 ratio 5 0 item 30 120 ratio 4 0 solve the fractional cover problem args items a list of items where each item has weight and value attributes capacity the maximum weight capacity of the knapsack returns the maximum value that can be obtained by selecting fractions of items to cover the knapsack s capacity raises valueerror if capacity is negative examples fractional_cover item 10 60 item 20 100 item 30 120 capacity 50 240 0 fractional_cover item 20 100 item 30 120 item 10 60 capacity 25 135 0 fractional_cover item 10 60 item 20 100 item 30 120 capacity 60 280 0 fractional_cover items item 5 30 item 10 60 item 15 90 capacity 30 180 0 fractional_cover items capacity 50 0 0 fractional_cover items item 10 60 capacity 5 30 0 fractional_cover items item 10 60 capacity 1 6 0 fractional_cover items item 10 60 capacity 0 0 0 fractional_cover items item 10 60 capacity 1 traceback most recent call last valueerror capacity cannot be negative sort the items by their value to weight ratio in descending order
from dataclasses import dataclass
from operator import attrgetter


@dataclass
class Item:
    weight: int
    value: int

    @property
    def ratio(self) -> float:
        
        return self.value / self.weight


def fractional_cover(items: list[Item], capacity: int) -> float:
    
    if capacity < 0:
        raise ValueError("Capacity cannot be negative")

    total_value = 0.0
    remaining_capacity = capacity

    
    for item in sorted(items, key=attrgetter("ratio"), reverse=True):
        if remaining_capacity == 0:
            break

        weight_taken = min(item.weight, remaining_capacity)
        total_value += weight_taken * item.ratio
        remaining_capacity -= weight_taken

    return total_value


if __name__ == "__main__":
    import doctest

    if result := doctest.testmod().failed:
        print(f"{result} test(s) failed")
    else:
        print("All tests passed")