From the following code, explain how it works and calculate the time complexity def bound_knapsack(i, current_weight, current_value, bound): if i == n: return current_value if current_weight + weights[i] <= capacity: # Include item i with_i = bound_knapsack(i + 1, current_weight + weights[i], current_value + values[i], bound) else: with_i = float("-inf") # Cannot include item i # Exclude item i without_i = bound_knapsack(i + 1, current_weight, current_value, bound) # Update bound (relaxatiole n) bound = max(bound, with_i, without_i) return bound # Example usage: n = 4 weights = [10, 20, 30, 40] values = [60, 100, 120, 240] capacity = 50 print("Branch and Bound:", bound_knapsack(0, 0, 0, float("-inf")))
From the following code, explain how it works and calculate the time complexity
def bound_knapsack(i, current_weight, current_value, bound):
if i == n:
return current_value
if current_weight + weights[i] <= capacity:
# Include item i
with_i = bound_knapsack(i + 1, current_weight + weights[i], current_value + values[i], bound)
else:
with_i = float("-inf") # Cannot include item i
# Exclude item i
without_i = bound_knapsack(i + 1, current_weight, current_value, bound)
# Update bound (relaxatiole n)
bound = max(bound, with_i, without_i)
return bound
# Example usage:
n = 4
weights = [10, 20, 30, 40]
values = [60, 100, 120, 240]
capacity = 50
print("Branch and Bound:", bound_knapsack(0, 0, 0, float("-inf")))
Step by step
Solved in 2 steps
