Greedy Algorithms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Interval {
5
    int start, finish;
6
};
7
8
int main() {
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    // Example intervals: [start, finish)
13
    vector<Interval> a = {
14
        {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16}
15
    };
16
17
    // Greedy rule: sort by earliest finish time, then pick non-overlapping intervals
18
    sort(a.begin(), a.end(), [](const Interval& x, const Interval& y){
19
        if (x.finish != y.finish) return x.finish < y.finish; // primary key: finish
20
        return x.start < y.start; // tie-breaker: earlier start (safe)
21
    });
22
23
    vector<Interval> chosen;
24
    int currentEnd = INT_MIN; // the finish time of the last chosen interval
25
26
    for (const auto& it : a) {
27
        if (it.start >= currentEnd) {
28
            // Non-overlapping; accept it and update the boundary
29
            chosen.push_back(it);
30
            currentEnd = it.finish;
31
        }
32
    }
33
34
    cout << "Maximum number of non-overlapping intervals: " << chosen.size() << "\n";
35
    cout << "Chosen intervals (start, finish):\n";
36
    for (auto &it : chosen) cout << it.start << " " << it.finish << "\n";
37
38
    return 0;
39
}
40

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Item {
5
    long long value;
6
    long long weight;
7
};
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    // Items: (value, weight) and knapsack capacity W. We can take fractions.
14
    vector<Item> items = {
15
        {60, 10}, {100, 20}, {120, 30}
16
    };
17
    long long W = 50;
18
19
    // Sort by decreasing value/weight. Avoid floating division when comparing.
20
    sort(items.begin(), items.end(), [](const Item& a, const Item& b){
21
        // Compare a.value/a.weight > b.value/b.weight via cross-multiplication
22
        // to avoid precision issues.
23
        return (__int128)a.value * b.weight > (__int128)b.value * a.weight;
24
    });
25
26
    long double totalValue = 0.0L;
27
    long long remaining = W;
28
29
    for (const auto& it : items) {
30
        if (remaining == 0) break;
31
        if (it.weight <= remaining) {
32
            // Take the whole item
33
            totalValue += it.value;
34
            remaining -= it.weight;
35
        } else {
36
            // Take a fraction to fill the bag
37
            long double fraction = (long double)remaining / (long double)it.weight;
38
            totalValue += (long double)it.value * fraction;
39
            remaining = 0;
40
            break;
41
        }
42
    }
43
44
    cout.setf(std::ios::fixed); cout << setprecision(6);
45
    cout << "Maximum fractional knapsack value: " << (double)totalValue << "\n";
46
    return 0;
47
}
48

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Node {
5
    long long freq;
6
    Node* left;
7
    Node* right;
8
    Node(long long f, Node* l=nullptr, Node* r=nullptr) : freq(f), left(l), right(r) {}
9
};
10
11
struct Cmp {
12
    bool operator()(const Node* a, const Node* b) const { return a->freq > b->freq; }
13
};
14
15
void buildCodes(Node* root, string path, unordered_map<long long, string>& codes) {
16
    if (!root) return;
17
    if (!root->left && !root->right) {
18
        // Leaf node: assign code
19
        codes[root->freq] = path.empty() ? "0" : path; // handle single-symbol edge case
20
        return;
21
    }
22
    buildCodes(root->left, path + "0", codes);
23
    buildCodes(root->right, path + "1", codes);
24
}
25
26
void freeTree(Node* root){ if(!root) return; freeTree(root->left); freeTree(root->right); delete root; }
27
28
int main(){
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    // Example frequencies for symbols A,B,C,D,E (we only use frequencies here)
33
    vector<pair<char,long long>> symbols = {{'A',45},{'B',13},{'C',12},{'D',16},{'E',9},{'F',5}};
34
35
    priority_queue<Node*, vector<Node*>, Cmp> pq;
36
    for (auto &p : symbols) pq.push(new Node(p.second));
37
38
    // Greedy: repeatedly merge two least frequent nodes
39
    while (pq.size() > 1) {
40
        Node* a = pq.top(); pq.pop();
41
        Node* b = pq.top(); pq.pop();
42
        Node* merged = new Node(a->freq + b->freq, a, b);
43
        pq.push(merged);
44
    }
45
46
    Node* root = pq.top();
47
48
    // Compute total weighted path length (expected code length times total weight)
49
    // Also build one possible code assignment (using left=0, right=1)
50
    unordered_map<long long, string> tmpCodes; // keyed by frequency for demo
51
    buildCodes(root, "", tmpCodes);
52
53
    // For reporting, map back to symbols by matching frequencies (note: duplicates need distinct nodes in real impl)
54
    long long totalCost = 0; // sum p_i * l_i scaled by frequency units
55
    cout << "Symbol : Code\n";
56
    for (auto &p : symbols) {
57
        // In production, store symbol in Node; for brevity, use freq to look up
58
        string code = tmpCodes[p.second];
59
        cout << p.first << " : " << code << "\n";
60
        totalCost += (long long)code.size() * p.second;
61
    }
62
    cout << "Total weighted code length: " << totalCost << "\n";
63
64
    freeTree(root);
65
    return 0;
66
}
67

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Edge { int to; long long w; };
5
6
vector<long long> dijkstra(int n, int s, const vector<vector<Edge>>& g) {
7
    const long long INF = (1LL<<62);
8
    vector<long long> dist(n, INF);
9
    vector<char> used(n, 0);
10
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
11
12
    dist[s] = 0;
13
    pq.push({0, s});
14
15
    while (!pq.empty()) {
16
        auto [du, u] = pq.top(); pq.pop();
17
        if (used[u]) continue; // skip outdated entries
18
        used[u] = 1;
19
        // Invariant: dist[u] is finalized and minimal
20
        for (auto e : g[u]) {
21
            if (dist[e.to] > du + e.w) {
22
                dist[e.to] = du + e.w;
23
                pq.push({dist[e.to], e.to});
24
            }
25
        }
26
    }
27
    return dist;
28
}
29
30
int main(){
31
    ios::sync_with_stdio(false);
32
    cin.tie(nullptr);
33
34
    int n = 5; // vertices 0..4
35
    vector<vector<Edge>> g(n);
36
    auto add = [&](int u, int v, long long w){ g[u].push_back({v,w}); g[v].push_back({u,w}); };
37
38
    // Undirected graph with nonnegative weights
39
    add(0,1,2); add(0,2,4); add(1,2,1); add(1,3,7); add(2,4,3); add(3,4,1);
40
41
    int s = 0;
42
    auto dist = dijkstra(n, s, g);
43
44
    cout << "Distances from source " << s << ":\n";
45
    for (int i = 0; i < n; ++i) cout << i << ": " << dist[i] << "\n";
46
47
    return 0;
48
}
49