Scribd
Upload
14 views1 page

3 Facknap

The document provides a Python program that implements a fractional Knapsack problem using a greedy algorithm. It defines an Item class and a function to calculate the maximum value that can be carried in a knapsack based on the value-to-weight ratio of items. The program includes complexity analysis, indicating that the overall time complexity is O(n log n) and the space complexity is O(n).

Uploaded by

shinchansbv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
14 views1 page

3 Facknap

The document provides a Python program that implements a fractional Knapsack problem using a greedy algorithm. It defines an Item class and a function to calculate the maximum value that can be carried in a knapsack based on the value-to-weight ratio of items. The program includes complexity analysis, indicating that the overall time complexity is O(n log n) and the space complexity is O(n).

Uploaded by

shinchansbv
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 1

# Write a program to solve a fractional Knapsack problem using a greedy

# method.

class Item:
"""Class to represent an item with value and weight."""
def __init__(self, value, weight):
self.value = value
self.weight = weight

def get_max_value(items, capacity):


"""Function to calculate the maximum value that can be carried in the
knapsack."""
# Sort the items by value-to-weight ratio in descending order
items.sort(key=lambda x: x.value / x.weight, reverse=True)

total_value = 0.0 # Initialize total value in knapsack


for item in items:
if capacity <= 0: # Break if knapsack is full
break

# If the item can be completely added to the knapsack


if item.weight <= capacity:
total_value += item.value
capacity -= item.weight
else:
# If we can't add the whole item, add the fractional part
total_value += item.value * (capacity / item.weight)
capacity = 0 # Knapsack is now full

return total_value

# Example usage:
if __name__ == "__main__":
items = [
Item(60, 10), # Item 1: value = 60, weight = 10
Item(100, 20), # Item 2: value = 100, weight = 20
Item(120, 30) # Item 3: value = 120, weight = 30
]
capacity = 50 # Maximum capacity of the knapsack

max_value = get_max_value(items, capacity)


print(f"Maximum value in the knapsack: {max_value:.2f}")

# Complexity Analysis

# Time Complexity:

# Sorting the items takesO(nlogn), where n is the number of items.


# The loop through the items takes O(n).
# Overall Time Complexity:O(nlogn).

# Space Complexity:

# The space used for storing items is O(n).


# The sorting operation may require additional space, but it is generally in-place.
# Overall Space Complexity: O(n).

You might also like