bhakti-thakur
39 lines
1.1 KiB
Python
39 lines
1.1 KiB
Python
# Fractional Knapsack using Greedy Method
|
|
|
|
class Item:
|
|
def __init__(self, value, weight):
|
|
self.value = value
|
|
self.weight = weight
|
|
|
|
def fractional_knapsack(items, capacity):
|
|
# Step 1: Sort items by value/weight ratio (descending)
|
|
items.sort(key=lambda x: x.value / x.weight, reverse=True)
|
|
|
|
total_value = 0.0 # total value in knapsack
|
|
remaining_capacity = capacity
|
|
|
|
# Step 2: Pick items greedily
|
|
for item in items:
|
|
if remaining_capacity >= item.weight:
|
|
# take full item
|
|
total_value += item.value
|
|
remaining_capacity -= item.weight
|
|
else:
|
|
# take fractional part
|
|
fraction = remaining_capacity / item.weight
|
|
total_value += item.value * fraction
|
|
break # knapsack is full
|
|
|
|
return total_value
|
|
|
|
# Example usage
|
|
if __name__ == "__main__":
|
|
values = [60, 100, 120]
|
|
weights = [10, 20, 30]
|
|
capacity = 50
|
|
|
|
items = [Item(v, w) for v, w in zip(values, weights)]
|
|
max_value = fractional_knapsack(items, capacity)
|
|
|
|
print("Maximum value in Knapsack =", max_value)
|