class Item:
def __init__(self, cost, weight):
self.cost = cost
self.weight = weight
self.ratio = cost / weight
def fractional_knapsack(capacity, items):
items.sort(key=lambda item: item.ratio, reverse=True)
total_cost = 0
for item in items:
if capacity <= 0:
break
if item.weight <= capacity:
total_cost += item.cost
capacity -= item.weight
else:
total_cost += item.cost * (capacity / item.weight)
capacity = 0
return total_cost
if __name__ == "__main__":
n = int(input("Enter the number of items: "))
capacity = int(input("Enter the capacity of the knapsack: "))
items = []
for _ in range(n):
cost, weight = map(int, input("Enter cost and weight of item (cost weight): ").split())
items.append(Item(cost, weight))
result = fractional_knapsack(capacity, items)
print(f"The maximum cost that can be obtained: {result}")
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter