Greedy Algorithm

Basics

A greedy algorithm is a problem-solving technique that builds up a solution piece by piece, always choosing the next piece that offers the most immediate benefit or the largest local gain. In simpler terms, a greedy algorithm makes a series of choices, each of which looks the best at the moment, without reconsidering those choices later on.

Key Characteristics:

• Local Optimization: At each step, the algorithm selects the option that seems the best right now (the local optimum) without worrying about whether it leads to the best global solution.

• Greedy Choice Property: The choice made by the algorithm at each step is the one that appears best according to some criterion. This decision is made without considering the future consequences.

• Optimal Substructure: A problem has an optimal substructure if an optimal solution to the problem contains optimal solutions to its subproblems.

Demonstration

Here’s a demonstration of the Greedy Algorithm applied to the fractional knapsack problem.

You have to maximize the total value of items that can be placed in a knapsack with a given weight capacity. You are given a list of items, each with a specific value and weight, and you can take fractions of items if necessary. The goal is to determine the optimal combination of items (or portions of items) to include in the knapsack so that the total value is as high as possible without exceeding the knapsack's weight limit.

Python Code

def fractional_knapsack(items, capacity):
    # Calculate value-to-weight ratio for each item and sort them in descending order
    items = sorted(items, key=lambda x: x[0]/x[1], reverse=True)
    
    total_value = 0.0  # Total value accumulated in the knapsack
    for value, weight in items:
        if capacity >= weight:
            # If the item can be fully added
            capacity -= weight
            total_value += value
        else:
            # Take the fraction of the remaining capacity
            total_value += value * (capacity / weight)
            break

    return total_value

# Example usage:
items = [(60, 10), (100, 20), (120, 30)]  # Each tuple is (value, weight)
capacity = 50

max_value = fractional_knapsack(items, capacity)
print(f"Maximum value in knapsack: {max_value}")

Output : Maximum value in knapsack: 240.0