Greedy Algorithms & Applications

function GREEDY(problem):
    solution = empty
    while problem not solved:
        // SELECT: Choose the best available option
        choice = SELECT_BEST_OPTION(problem)

        // FEASIBILITY: Check if choice is valid
        if IS_FEASIBLE(solution, choice):
            // INCLUDE: Add choice to solution
            solution = solution + choice

    return solution

function FRACTIONAL_KNAPSACK(W, weights[], profits[], n):
    // Calculate ratios and sort
    for i = 1 to n:
        ratio[i] = profits[i] / weights[i]

    // Sort items by ratio in decreasing order
    SORT_BY_RATIO_DESCENDING(items)

    totalProfit = 0
    remainingCapacity = W

    for each item in sorted order:
        if weights[item] <= remainingCapacity:
            // Take complete item
            totalProfit += profits[item]
            remainingCapacity -= weights[item]
        else:
            // Take fraction of item
            fraction = remainingCapacity / weights[item]
            totalProfit += profits[item] * fraction
            remainingCapacity = 0
            break

    return totalProfit

function PRIMS(graph, start):
    MST = empty set
    visited = {start}
    edges = all edges from start

    while |visited| < |V|:
        // Find minimum weight edge to unvisited vertex
        (u, v, weight) = MIN_EDGE where u in visited, v not in visited

        MST.add((u, v, weight))
        visited.add(v)

        // Add all edges from v to unvisited vertices
        for each edge (v, w) where w not in visited:
            edges.add((v, w))

    return MST

function KRUSKALS(graph):
    MST = empty set
    edges = all edges sorted by weight ascending

    // Initialize Union-Find (each vertex in own set)
    for each vertex v:
        MAKE_SET(v)

    for each edge (u, v, weight) in sorted edges:
        if FIND(u) ≠ FIND(v):  // Different sets = no cycle
            MST.add((u, v, weight))
            UNION(u, v)

        if |MST| == |V| - 1:
            break

    return MST