#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Activity {
    int start, finish, index;
    
    Activity(int s, int f, int i) : start(s), finish(f), index(i) {}
};

class ActivitySelection {
public:
    // Greedy approach: select activity that finishes earliest
    vector<int> selectActivities(vector<Activity>& activities) {
        // Sort activities by finish time
        sort(activities.begin(), activities.end(), 
             [](const Activity& a, const Activity& b) {
                 return a.finish < b.finish;
             });
        
        vector<int> result;
        result.push_back(activities[0].index);
        int lastFinish = activities[0].finish;
        
        cout << "Selected activities (in order of selection):" << endl;
        cout << "Activity " << activities[0].index 
             << ": [" << activities[0].start << ", " << activities[0].finish << "]" << endl;
        
        // Consider remaining activities
        for (int i = 1; i < activities.size(); i++) {
            // If this activity starts after the last selected activity finishes
            if (activities[i].start >= lastFinish) {
                result.push_back(activities[i].index);
                lastFinish = activities[i].finish;
                cout << "Activity " << activities[i].index 
                     << ": [" << activities[i].start << ", " << activities[i].finish << "]" << endl;
            }
        }
        
        return result;
    }
    
    // Recursive greedy approach
    void selectActivitiesRecursive(vector<Activity>& activities, int i, 
                                   vector<int>& result) {
        int j = i + 1;
        
        // Find next compatible activity
        while (j < activities.size() && activities[j].start < activities[i].finish) {
            j++;
        }
        
        if (j < activities.size()) {
            result.push_back(activities[j].index);
            selectActivitiesRecursive(activities, j, result);
        }
    }
    
    void printActivities(const vector<Activity>& activities) {
        cout << "Available activities:" << endl;
        for (const auto& activity : activities) {
            cout << "Activity " << activity.index 
                 << ": [" << activity.start << ", " << activity.finish << "]" << endl;
        }
        cout << endl;
    }
};

int main() {
    vector<Activity> activities = {
        Activity(1, 4, 1),
        Activity(3, 5, 2),
        Activity(0, 6, 3),
        Activity(5, 7, 4),
        Activity(8, 9, 5),
        Activity(5, 9, 6)
    };
    
    ActivitySelection as;
    as.printActivities(activities);
    
    vector<int> selected = as.selectActivities(activities);
    
    cout << "\nTotal activities selected: " << selected.size() << endl;
    cout << "Activity indices: ";
    for (int id : selected) {
        cout << id << " ";
    }
    cout << endl;
    
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Item {
    int value, weight;
    double ratio;
    int index;
    
    Item(int v, int w, int i) : value(v), weight(w), index(i) {
        ratio = (double)v / w;
    }
};

class FractionalKnapsack {
public:
    double solve(vector<Item>& items, int capacity) {
        // Sort items by value-to-weight ratio in descending order
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        double totalValue = 0.0;
        int currentWeight = 0;
        
        cout << "Items sorted by value/weight ratio:" << endl;
        for (const auto& item : items) {
            cout << "Item " << item.index << ": value=" << item.value 
                 << ", weight=" << item.weight << ", ratio=" << item.ratio << endl;
        }
        cout << endl;
        
        cout << "Knapsack filling process:" << endl;
        
        for (auto& item : items) {
            if (currentWeight + item.weight <= capacity) {
                // Take the whole item
                currentWeight += item.weight;
                totalValue += item.value;
                cout << "Take whole Item " << item.index 
                     << " (weight: " << item.weight << ", value: " << item.value << ")" << endl;
            } else {
                // Take fraction of the item
                int remainingCapacity = capacity - currentWeight;
                if (remainingCapacity > 0) {
                    double fraction = (double)remainingCapacity / item.weight;
                    totalValue += item.value * fraction;
                    cout << "Take " << fraction << " of Item " << item.index 
                         << " (weight: " << remainingCapacity << ", value: " 
                         << item.value * fraction << ")" << endl;
                }
                break;
            }
        }
        
        return totalValue;
    }
    
    // Alternative implementation with detailed tracking
    struct Solution {
        double totalValue;
        vector<pair<int, double>> itemFractions; // (item_index, fraction_taken)
    };
    
    Solution solveDetailed(vector<Item>& items, int capacity) {
        sort(items.begin(), items.end(), 
             [](const Item& a, const Item& b) {
                 return a.ratio > b.ratio;
             });
        
        Solution solution;
        solution.totalValue = 0.0;
        int currentWeight = 0;
        
        for (auto& item : items) {
            if (currentWeight + item.weight <= capacity) {
                // Take whole item
                currentWeight += item.weight;
                solution.totalValue += item.value;
                solution.itemFractions.push_back({item.index, 1.0});
            } else {
                // Take fraction
                int remainingCapacity = capacity - currentWeight;
                if (remainingCapacity > 0) {
                    double fraction = (double)remainingCapacity / item.weight;
                    solution.totalValue += item.value * fraction;
                    solution.itemFractions.push_back({item.index, fraction});
                }
                break;
            }
        }
        
        return solution;
    }
    
    void printSolution(const Solution& solution) {
        cout << "\nDetailed solution:" << endl;
        cout << "Total value: " << solution.totalValue << endl;
        cout << "Items taken:" << endl;
        for (const auto& itemFraction : solution.itemFractions) {
            cout << "Item " << itemFraction.first << ": " 
                 << (itemFraction.second * 100) << "%" << endl;
        }
    }
};

int main() {
    vector<Item> items = {
        Item(60, 10, 1),
        Item(100, 20, 2),
        Item(120, 30, 3)
    };
    
    int capacity = 50;
    
    FractionalKnapsack fk;
    
    cout << "Knapsack capacity: " << capacity << endl;
    cout << "Available items:" << endl;
    for (const auto& item : items) {
        cout << "Item " << item.index << ": value=" << item.value 
             << ", weight=" << item.weight << endl;
    }
    cout << endl;
    
    double maxValue = fk.solve(items, capacity);
    cout << "\nMaximum value: " << maxValue << endl;
    
    // Reset items for detailed solution
    vector<Item> items2 = {
        Item(60, 10, 1),
        Item(100, 20, 2),
        Item(120, 30, 3)
    };
    
    auto solution = fk.solveDetailed(items2, capacity);
    fk.printSolution(solution);
    
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

struct Node {
    char character;
    int frequency;
    Node* left;
    Node* right;
    
    Node(char c, int f) : character(c), frequency(f), left(nullptr), right(nullptr) {}
    Node(int f) : character('\0'), frequency(f), left(nullptr), right(nullptr) {}
};

struct Compare {
    bool operator()(Node* a, Node* b) {
        if (a->frequency == b->frequency) {
            return a->character > b->character; // For deterministic results
        }
        return a->frequency > b->frequency;
    }
};

class HuffmanCoding {
public:
    Node* buildHuffmanTree(vector<pair<char, int>>& frequencies) {
        priority_queue<Node*, vector<Node*>, Compare> pq;
        
        // Create leaf nodes and add to priority queue
        for (auto& freq : frequencies) {
            pq.push(new Node(freq.first, freq.second));
        }
        
        cout << "Building Huffman Tree:" << endl;
        
        // Build the tree
        while (pq.size() > 1) {
            Node* right = pq.top(); pq.pop();
            Node* left = pq.top(); pq.pop();
            
            Node* merged = new Node(left->frequency + right->frequency);
            merged->left = left;
            merged->right = right;
            
            cout << "Merge nodes with frequencies " << left->frequency 
                 << " and " << right->frequency << " -> " << merged->frequency << endl;
            
            pq.push(merged);
        }
        
        return pq.top();
    }
    
    void generateCodes(Node* root, string code, unordered_map<char, string>& codes) {
        if (!root) return;
        
        // Leaf node
        if (!root->left && !root->right) {
            codes[root->character] = code.empty() ? "0" : code;
            return;
        }
        
        generateCodes(root->left, code + "0", codes);
        generateCodes(root->right, code + "1", codes);
    }
    
    void printCodes(const unordered_map<char, string>& codes, 
                    const vector<pair<char, int>>& frequencies) {
        cout << "\nHuffman Codes:" << endl;
        cout << "Character | Frequency | Code" << endl;
        cout << "----------|-----------|-----" << endl;
        
        int totalBits = 0;
        int totalOriginalBits = 0;
        
        for (const auto& freq : frequencies) {
            char c = freq.first;
            int f = freq.second;
            string code = codes.at(c);
            
            cout << "    " << c << "     |     " << f << "     | " << code << endl;
            totalBits += f * code.length();
            totalOriginalBits += f * 8; // Assuming 8 bits per character originally
        }
        
        cout << "\nCompression Analysis:" << endl;
        cout << "Original bits: " << totalOriginalBits << endl;
        cout << "Huffman bits: " << totalBits << endl;
        cout << "Compression ratio: " << (double)totalBits / totalOriginalBits << endl;
    }
    
    string encode(const string& text, const unordered_map<char, string>& codes) {
        string encoded = "";
        for (char c : text) {
            encoded += codes.at(c);
        }
        return encoded;
    }
    
    string decode(const string& encoded, Node* root) {
        string decoded = "";
        Node* current = root;
        
        for (char bit : encoded) {
            if (bit == '0') {
                current = current->left;
            } else {
                current = current->right;
            }
            
            // Reached leaf node
            if (!current->left && !current->right) {
                decoded += current->character;
                current = root;
            }
        }
        
        return decoded;
    }
};

int main() {
    vector<pair<char, int>> frequencies = {
        {'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}
    };
    
    HuffmanCoding hc;
    
    cout << "Character frequencies:" << endl;
    for (auto& freq : frequencies) {
        cout << freq.first << ": " << freq.second << endl;
    }
    cout << endl;
    
    Node* root = hc.buildHuffmanTree(frequencies);
    
    unordered_map<char, string> codes;
    hc.generateCodes(root, "", codes);
    hc.printCodes(codes, frequencies);
    
    // Test encoding and decoding
    string text = "abcdef";
    string encoded = hc.encode(text, codes);
    string decoded = hc.decode(encoded, root);
    
    cout << "\nTest encoding/decoding:" << endl;
    cout << "Original: " << text << endl;
    cout << "Encoded: " << encoded << endl;
    cout << "Decoded: " << decoded << endl;
    
    return 0;
}