Greedy Algorithms

public class ActivitySelection {
    // Function to select maximum activities
    public static int maxActivities(int[] start, int[] finish) {
        int n = start.length;
        
        // Sort activities by finish time
        // (Assuming activities are already sorted by finish time for simplicity)
        
        int count = 1;  // First activity is always selected
        int lastFinish = finish[0];
        
        // Consider rest of the activities
        for (int i = 1; i < n; i++) {
            // If this activity has start time greater than or equal
            // to the finish time of previously selected activity,
            // then select it
            if (start[i] >= lastFinish) {
                count++;
                lastFinish = finish[i];
            }
        }
        
        return count;
    }
    
    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        
        System.out.println("Maximum number of activities: " + maxActivities(start, finish));
    }
}

public class FractionalKnapsack {
    // Item class
    static class Item {
        int value;
        int weight;
        
        public Item(int value, int weight) {
            this.value = value;
            this.weight = weight;
        }
        
        // Value per unit weight
        public double ratio() {
            return (double) value / weight;
        }
    }
    
    // Function to get maximum value
    public static double getMaxValue(Item[] items, int capacity) {
        // Sort items by value-to-weight ratio in non-increasing order
        Arrays.sort(items, (a, b) -> Double.compare(b.ratio(), a.ratio()));
        
        double totalValue = 0;
        int currentWeight = 0;
        
        for (Item item : items) {
            // If adding the complete item doesn't exceed capacity
            if (currentWeight + item.weight <= capacity) {
                currentWeight += item.weight;
                totalValue += item.value;
            } else {
                // Add a fraction of the item
                int remainingCapacity = capacity - currentWeight;
                totalValue += item.value * ((double) remainingCapacity / item.weight);
                break;
            }
        }
        
        return totalValue;
    }
    
    public static void main(String[] args) {
        Item[] items = {
            new Item(60, 10),
            new Item(100, 20),
            new Item(120, 30)
        };
        int capacity = 50;
        
        System.out.println("Maximum value: " + getMaxValue(items, capacity));
    }
}

import heapq

class Node:
    def __init__(self, freq, symbol, left=None, right=None):
        self.freq = freq
        self.symbol = symbol
        self.left = left
        self.right = right
        self.huff = ''
        
    def __lt__(self, nxt):
        return self.freq < nxt.freq
        
def print_nodes(node, val=''):
    # Huffman code for current node
    new_val = val + str(node.huff)
    
    # If node is not an edge node, traverse inside it
    if node.left:
        print_nodes(node.left, new_val)
    if node.right:
        print_nodes(node.right, new_val)
        
    # If node is edge node, print its huffman code
    if not node.left and not node.right:
        print(f"{node.symbol} -> {new_val}")

def huffman_coding(chars, freq):
    nodes = []
    
    # Create a leaf node for each character and add it to the priority queue
    for i in range(len(chars)):
        heapq.heappush(nodes, Node(freq[i], chars[i]))
    
    # Build Huffman Tree
    while len(nodes) > 1:
        # Remove two nodes of highest priority (lowest frequency)
        left = heapq.heappop(nodes)
        right = heapq.heappop(nodes)
        
        # Assign directional value to these nodes
        left.huff = 0
        right.huff = 1
        
        # Create a new internal node with these two nodes as children
        # and with frequency equal to the sum of the two nodes' frequencies
        new_node = Node(left.freq + right.freq, left.symbol + right.symbol, left, right)
        
        heapq.heappush(nodes, new_node)
    
    # Print Huffman codes
    print_nodes(nodes[0])

# Example usage
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [5, 9, 12, 13, 16, 45]
huffman_coding(chars, freq)