Python Program for Fractional Knapsack Problem
Given the weights and profits of N items, in the form of {profit, weight} put these items in a knapsack of capacity W to get the maximum total profit in the knapsack. In Fractional Knapsack, we can break items to maximize the total value of the knapsack.
Example :
Input: arr[] = {{60, 10}, {100, 20}, {120, 30}}, W = 50
Output: 240
Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240Input: arr[] = {{500, 30}}, W = 10
Output: 166.667
Python Program for Fractional Knapsack Problem
Below, are the examples of Python programs for the Fractional Knapsack Problem.
Fractional Knapsack Problem Using Greedy Algorithm
Illustration
Consider the example: arr[] = {{100, 20}, {60, 10}, {120, 30}}, W = 50.
Sorting: Initially sort the array based on the profit/weight ratio. The sorted array will be {{60, 10}, {100, 20}, {120, 30}}.
- For i = 0, weight = 10 which is less than W. So add this element in the knapsack. profit = 60 and remaining W = 50 – 10 = 40.
- For i = 1, weight = 20 which is less than W. So add this element too. profit = 60 + 100 = 160 and remaining W = 40 – 20 = 20.
- For i = 2, weight = 30 is greater than W. So add 20/30 fraction = 2/3 fraction of the element. Therefore profit = 2/3 * 120 + 160 = 80 + 160 = 240 and remaining W becomes 0.
So the final profit becomes 240 for W = 50.
Follow the given steps to solve the problem using the above approach:
- Figure out the ratio of profit to weight for each item.
- Arrange all the items from highest to lowest ratio.
- Start with an empty result and the total capacity you have.
- For each item in the sorted order:
- If you can fit the whole item into the remaining capacity, add its value to the result.
- Otherwise, add as much of the item as you can and stop.
- Finally, return the total result.
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
# Calculate the value-to-weight ratio for each item
self.ratio = value / weight
def fractional_knapsack(items, capacity):
# Sort items by their value-to-weight ratio in non-increasing order
items.sort(key=lambda x: x.ratio, reverse=True)
total_value = 0
# Initialize remaining capacity of the knapsack
remaining_capacity = capacity
# Iterate through the sorted items list
for item in items:
if remaining_capacity <= 0:
break
# Calculate fraction of the item that fits into the knapsack
fraction = min(1, remaining_capacity / item.weight)
# Update total value and remaining capacity
total_value += fraction * item.value
remaining_capacity -= fraction * item.weight
# Return total maximum value obtained
return round(total_value, 2)
# Example usage
items = [
Item(10, 60),
Item(20, 100),
Item(30, 120)
]
capacity = 50
print("Maximum Value that can be Obtained is", fractional_knapsack(items, capacity))
Output
Maximum value that can be obtained is 240.0
Time Complexity: O(n log n + n). O(n log n )
Space Complexity: O(1)
Fractional Knapsack Problem Using Dynamic Programming
Illustration
Consider the example: arr[] = {{100, 20}, {60, 10}, {120, 30}}, W = 50.
- Arrange items based on their value-to-weight ratio: {60, 10}, {100, 20}, {120, 30}.
- Start with first item: Its weight is 10, less than the capacity (50). Add it to the knapsack, profit becomes 60, and remaining capacity is 40.
- Move to next item: Weight is 20, still within remaining capacity. Add it, profit becomes 160, and remaining capacity is 20.
- Last item: Its weight exceeds the remaining capacity. Add a fraction (2/3) of its weight to fill the knapsack. Profit becomes 240, and the knapsack is full (remaining capacity is 0).
So the final profit becomes 240 for W = 50
Follow the given steps to solve the problem using the above approach:
- It defines a class
Item
with variableweight
andvalue
to represent each item. - The function
fractional_knapsack_dynamic
takes a list of items and the knapsack capacity as input. - It initializes a dynamic programming array to store the maximum value achieved for each capacity.
- It iterates through each capacity and each item, updating the maximum value achievable.
- Finally, it returns the maximum profit achieved using dynamic programming.
class Item:
def __init__(self, weight, value):
self.weight = weight
self.value = value
def fractional_knapsack_dynamic(items, capacity):
n = len(items)
# Initialize dp array to store maximum value achieved for each capacity
dp = [0] * (capacity + 1)
# Iterate from 1 to capacity
for i in range(1, capacity + 1):
max_value = 0
# Iterate through each item
for j in range(n):
if items[j].weight <= i:
# Update max_value with the maximum value achieved for the current capacity
max_value = max(max_value, dp[i - items[j].weight] + items[j].value)
# Update dp array with the maximum value achieved for current capacity
dp[i] = max_value
# Return maximum profit achieved using dynamic programming
return dp[capacity]
# Example usage
items = [
Item(10, 60),
Item(20, 100),
Item(30, 120)
]
capacity = 50
print("Maximum Value Obtained Using Dynamic Approach is", fractional_knapsack_dynamic(items, capacity))
Output
Maximum value obtained using dynamic approach is 300
Time Complexity: O(n * capacity)
Space Complexity: O(capacity)