0/1 Knapsack Problem using Greedy Technique in Python

 

The 0/1 knapsack problem can also be solved using an iterative technique in Python. One way to do this is by using a greedy approach, where the items are sorted in decreasing order of their value-to-weight ratio and then added to the knapsack one by one, as long as the weight constraint is not exceeded.

Here is the code for a function that solves the 0/1 knapsack problem using a greedy approach in Python:

def knapsack(weight, value, W):
  # Zip the weight and value lists into a list of tuples
  items = list(zip(weight, value))
  # Sort the list of tuples by the value-to-weight ratio in decreasing order
  items.sort(key=lambda x: x[1] / x[0], reverse=True)
  
  # Initialize the total value and weight of the knapsack to zero
  total_value = 0
  total_weight = 0
  # Iterate over the sorted items
  for w, v in items:
    # If the weight of the item is less than or equal to the remaining weight, add it to the knapsack
    if total_weight + w <= W:
      total_value += v
      total_weight += w
    # Otherwise, add a fraction of the item to the knapsack to fill it up
    else:
      fraction = (W - total_weight) / w
      total_value += fraction * v
      break
  
  # Return the total value of the knapsack
  return total_value

# Test the function with a sample set of items and a weight constraint
weight = [1, 3, 4, 5]
value = [15, 50, 60, 90]
W = 8
print(knapsack(weight, value, W))  # Output: 100

This implementation of the 0/1 knapsack problem using a greedy approach has a time complexity of O(n log n), where n is the number of items. It is a simple and efficient solution for finding a near-optimal solution to the 0/1 knapsack problem, but it may not always find the globally optimal solution.