Number Theory

Primality Testing via Trial Division

#include <iostream>
using namespace std;

bool isPrime(int num) {
    if (num < 2) return false;
    for (int d = 2; d <= num / d; ++d)
        if (num % d == 0) return false;
    return true;
}

int main() {
    int queries;
    cin >> queries;
    while (queries--) {
        int val;
        cin >> val;
        cout << (isPrime(val) ? "Yes" : "No") << endl;
    }
    return 0;
}

Prime Factorization

#include <iostream>
using namespace std;

void factorize(int n) {
    for (int d = 2; d <= n / d; ++d) {
        if (n % d == 0) {
            int exp = 0;
            while (n % d == 0) {
                ++exp;
                n /= d;
            }
            cout << d << ' ' << exp << endl;
        }
    }
    if (n > 1) cout << n << " 1" << endl;
}

int main() {
    int count;
    cin >> count;
    while (count--) {
        int val;
        cin >> val;
        factorize(val);
        cout << endl;
    }
    return 0;
}

Sieve of Eratosthenes

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

void sieve(int limit) {
    vector<bool> isPrime(limit + 1, true);
    vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (isPrime[i]) {
            primes.push_back(i);
            for (long long j = (long long)i * i; j <= limit; j += i)
                isPrime[j] = false;
        }
    }
    for (int p : primes) cout << p << ' ';
    cout << endl << primes.size();
}

int main() {
    int n;
    cin >> n;
    sieve(n);
    return 0;
}

Linear Sieve

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

void linearSieve(int limit) {
    vector<int> primes;
    vector<bool> composite(limit + 1, false);
    for (int i = 2; i <= limit; ++i) {
        if (!composite[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p > limit) break;
            composite[i * p] = true;
            if (i % p == 0) break;
        }
    }
    cout << primes.size();
}

int main() {
    int n;
    cin >> n;
    linearSieve(n);
    return 0;
}

Divisors via Trial Division

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

void listDivisors(int x) {
    vector<int> divisors;
    for (int d = 1; d <= x / d; ++d) {
        if (x % d == 0) {
            divisors.push_back(d);
            if (d != x / d) divisors.push_back(x / d);
        }
    }
    sort(divisors.begin(), divisors.end());
    for (int d : divisors) cout << d << ' ';
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int val;
        cin >> val;
        listDivisors(val);
        cout << endl;
    }
    return 0;
}

Count of Divisors

#include <iostream>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> factorCount;
    while (n--) {
        int val;
        cin >> val;
        for (int d = 2; d <= val / d; ++d)
            while (val % d == 0) {
                ++factorCount[d];
                val /= d;
            }
        if (val > 1) ++factorCount[val];
    }
    long long result = 1;
    for (auto &[prime, cnt] : factorCount)
        result = result * (cnt + 1) % MOD;
    cout << result;
    return 0;
}

Sum of Divisors

#include <iostream>
#include <unordered_map>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    int n;
    cin >> n;
    unordered_map<int, int> factorCount;
    while (n--) {
        int val;
        cin >> val;
        for (int d = 2; d <= val / d; ++d)
            while (val % d == 0) {
                ++factorCount[d];
                val /= d;
            }
        if (val > 1) ++factorCount[val];
    }
    long long total = 1;
    for (auto &[prime, cnt] : factorCount) {
        long long term = 1, power = 1;
        for (int i = 0; i < cnt; ++i) {
            power = power * prime % MOD;
            term = (term + power) % MOD;
        }
        total = total * term % MOD;
    }
    cout << total;
    return 0;
}

Greatest Common Divisor

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        cout << gcd(x, y) << endl;
    }
    return 0;
}

Least Common Multiple

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int x, y;
        cin >> x >> y;
        cout << x / gcd(x, y) * y << endl;
    }
    return 0;
}

Euler's Toteint Function

#include <iostream>
using namespace std;

int phi(int n) {
    int result = n;
    for (int d = 2; d <= n / d; ++d) {
        if (n % d == 0) {
            while (n % d == 0) n /= d;
            result -= result / d;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int val;
        cin >> val;
        cout << phi(val) << endl;
    }
    return 0;
}

Fast Exponentiation

#include <iostream>
using namespace std;

long long power(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    while (exp) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a, b, p;
        cin >> a >> b >> p;
        cout << power(a, b, p) << endl;
    }
    return 0;
}

Modular Inverse via Fermat's Theorem

#include <iostream>
using namespace std;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1 % mod;
    while (exp) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        long long a, p;
        cin >> a >> p;
        if (a % p == 0) cout << "impossible" << endl;
        else cout << modPow(a, p - 2, p) << endl;
    }
    return 0;
}

Extended Euclidean Algorithm

#include <iostream>
using namespace std;

int extendedGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = extendedGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, b, x, y;
        cin >> a >> b;
        extendedGcd(a, b, x, y);
        cout << x << ' ' << y << endl;
    }
    return 0;
}

Modular Inverse via Extneded Euclidean Algorithm

#include <iostream>
using namespace std;

int extendedGcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int d = extendedGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a, p, x, y;
        cin >> a >> p;
        int d = extendedGcd(a, p, x, y);
        if (d != 1) cout << "impossible" << endl;
        else cout << ((long long)x % p + p) % p << endl;
    }
    return 0;
}

Binomial Coefficients (Small Range)

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7, MAX = 2000;

int main() {
    vector<vector<int>> comb(MAX + 1, vector<int>(MAX + 1, 0));
    for (int i = 0; i <= MAX; ++i) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; ++j)
            comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
    }
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << comb[n][k] << endl;
    }
    return 0;
}

Binomial Coefficients (Large Range)

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7, MAX = 1e5;

long long modPow(long long base, long long exp) {
    long long result = 1 % MOD;
    while (exp) {
        if (exp & 1) result = result * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    vector<long long> fact(MAX + 1, 1), invFact(MAX + 1, 1);
    for (int i = 1; i <= MAX; ++i) {
        fact[i] = fact[i-1] * i % MOD;
        invFact[i] = modPow(fact[i], MOD - 2);
    }
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        cout << fact[n] * invFact[k] % MOD * invFact[n-k] % MOD << endl;
    }
    return 0;
}

Graph Theory

Topological Sorting

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

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<vector<int>> adj(vertices + 1);
    vector<int> indegree(vertices + 1, 0);
    while (edges--) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        ++indegree[v];
    }
    queue<int> q;
    for (int i = 1; i <= vertices; ++i)
        if (indegree[i] == 0) q.push(i);
    vector<int> order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u])
            if (--indegree[v] == 0) q.push(v);
    }
    if (order.size() != vertices) cout << -1;
    else for (int u : order) cout << u << ' ';
    return 0;
}

Dijkstra's Algorithm (Naive)

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

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<vector<pair<int, int>>> graph(vertices + 1);
    while (edges--) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }
    vector<int> dist(vertices + 1, INT_MAX);
    vector<bool> visited(vertices + 1, false);
    dist[1] = 0;
    for (int i = 0; i < vertices; ++i) {
        int u = -1;
        for (int j = 1; j <= vertices; ++j)
            if (!visited[j] && (u == -1 || dist[j] < dist[u]))
                u = j;
        if (dist[u] == INT_MAX) break;
        visited[u] = true;
        for (auto &[v, w] : graph[u])
            if (dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
    }
    cout << (dist[vertices] == INT_MAX ? -1 : dist[vertices]);
    return 0;
}

Bellman-Ford Algorithm

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

struct Edge { int u, v, weight; };

int main() {
    int vertices, edges, limit;
    cin >> vertices >> edges >> limit;
    vector<Edge> edgeList(edges);
    for (int i = 0; i < edges; ++i)
        cin >> edgeList[i].u >> edgeList[i].v >> edgeList[i].weight;
    vector<int> dist(vertices + 1, INT_MAX);
    dist[1] = 0;
    for (int i = 0; i < limit; ++i) {
        vector<int> prev = dist;
        bool updated = false;
        for (auto &e : edgeList)
            if (prev[e.u] != INT_MAX && prev[e.u] + e.weight < dist[e.v]) {
                dist[e.v] = prev[e.u] + e.weight;
                updated = true;
            }
        if (!updated) break;
    }
    cout << (dist[vertices] == INT_MAX ? "impossible" : to_string(dist[vertices]));
    return 0;
}

SPFA Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<vector<pair<int, int>>> graph(vertices + 1);
    while (edges--) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
    }
    vector<int> dist(vertices + 1, INT_MAX);
    vector<bool> inQueue(vertices + 1, false);
    queue<int> q;
    dist[1] = 0;
    q.push(1);
    inQueue[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        for (auto &[v, w] : graph[u])
            if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
    }
    cout << (dist[vertices] == INT_MAX ? "impossible" : to_string(dist[vertices]));
    return 0;
}

Floyd-Warshall Algorithm

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

int main() {
    int vertices, edges, queries;
    cin >> vertices >> edges >> queries;
    vector<vector<long long>> dist(vertices + 1, vector<long long>(vertices + 1, LLONG_MAX / 2));
    for (int i = 1; i <= vertices; ++i) dist[i][i] = 0;
    while (edges--) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], (long long)w);
    }
    for (int k = 1; k <= vertices; ++k)
        for (int i = 1; i <= vertices; ++i)
            for (int j = 1; j <= vertices; ++j)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
    while (queries--) {
        int u, v;
        cin >> u >> v;
        if (dist[u][v] > LLONG_MAX / 3) cout << "impossible" << endl;
        else cout << dist[u][v] << endl;
    }
    return 0;
}

Prim's Algorithm (Naive)

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

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<vector<pair<int, int>>> graph(vertices + 1);
    while (edges--) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].emplace_back(v, w);
        graph[v].emplace_back(u, w);
    }
    vector<int> minEdge(vertices + 1, INT_MAX);
    vector<bool> inMST(vertices + 1, false);
    minEdge[1] = 0;
    int totalWeight = 0, nodesIncluded = 0;
    for (int i = 0; i < vertices; ++i) {
        int u = -1;
        for (int j = 1; j <= vertices; ++j)
            if (!inMST[j] && (u == -1 || minEdge[j] < minEdge[u]))
                u = j;
        if (minEdge[u] == INT_MAX) break;
        inMST[u] = true;
        totalWeight += minEdge[u];
        ++nodesIncluded;
        for (auto &[v, w] : graph[u])
            if (w < minEdge[v]) minEdge[v] = w;
    }
    cout << (nodesIncluded == vertices ? to_string(totalWeight) : "impossible");
    return 0;
}

Kruskal's Algorithm

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

struct Edge { int u, v, weight; };
vector<int> parent;

int findSet(int x) {
    return parent[x] == x ? x : parent[x] = findSet(parent[x]);
}

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    vector<Edge> edgeList(edges);
    for (int i = 0; i < edges; ++i)
        cin >> edgeList[i].u >> edgeList[i].v >> edgeList[i].weight;
    sort(edgeList.begin(), edgeList.end(), [](Edge &a, Edge &b) { return a.weight < b.weight; });
    parent.resize(vertices + 1);
    for (int i = 1; i <= vertices; ++i) parent[i] = i;
    int totalWeight = 0, edgesUsed = 0;
    for (auto &e : edgeList) {
        int setU = findSet(e.u), setV = findSet(e.v);
        if (setU != setV) {
            parent[setV] = setU;
            totalWeight += e.weight;
            if (++edgesUsed == vertices - 1) break;
        }
    }
    cout << (edgesUsed == vertices - 1 ? to_string(totalWeight) : "impossible");
    return 0;
}

Greedy Algorithms

Interval Point Selection

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.second < b.second; });
    int points = 0, last = -2e9;
    for (auto &[l, r] : intervals)
        if (last < l) {
            ++points;
            last = r;
        }
    cout << points;
    return 0;
}

Maximum Non-Overlapping Intervals

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;
    sort(intervals.begin(), intervals.end(), [](auto &a, auto &b) { return a.second < b.second; });
    int count = 0, last = -2e9;
    for (auto &[l, r] : intervals)
        if (last < l) {
            ++count;
            last = r;
        }
    cout << count;
    return 0;
}

Interval Grouping

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

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (auto &[l, r] : intervals) {
        if (minHeap.empty() || minHeap.top() >= l)
            minHeap.push(r);
        else {
            minHeap.pop();
            minHeap.push(r);
        }
    }
    cout << minHeap.size();
    return 0;
}

Interval Coverage

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

int main() {
    int start, end, n;
    cin >> start >> end >> n;
    vector<pair<int, int>> intervals(n);
    for (auto &[l, r] : intervals) cin >> l >> r;
    sort(intervals.begin(), intervals.end());
    int segments = 0, i = 0;
    bool covered = false;
    while (i < n) {
        int furthest = -2e9, j = i;
        while (j < n && intervals[j].first <= start) {
            furthest = max(furthest, intervals[j].second);
            ++j;
        }
        if (furthest < start) break;
        ++segments;
        start = furthest;
        if (start >= end) { covered = true; break; }
        i = j;
    }
    cout << (covered ? to_string(segments) : "-1");
    return 0;
}

Data Structures

KMP Algorithm

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

int main() {
    string pattern, text;
    cin >> pattern >> text;
    int m = pattern.size(), n = text.size();
    vector<int> lps(m, 0);
    for (int i = 1, len = 0; i < m; ) {
        if (pattern[i] == pattern[len]) lps[i++] = ++len;
        else if (len) len = lps[len-1];
        else lps[i++] = 0;
    }
    vector<int> matches;
    for (int i = 0, j = 0; i < n; ) {
        if (text[i] == pattern[j]) { ++i; ++j; }
        if (j == m) {
            matches.push_back(i - j);
            j = lps[j-1];
        } else if (i < n && text[i] != pattern[j]) {
            if (j) j = lps[j-1];
            else ++i;
        }
    }
    for (int pos : matches) cout << pos << ' ';
    return 0;
}

Z-Function

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

int main() {
    string pattern, text;
    cin >> pattern >> text;
    string combined = pattern + '#' + text;
    int len = combined.size();
    vector<int> z(len, 0);
    for (int i = 1, l = 0, r = 0; i < len; ++i) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < len && combined[z[i]] == combined[i + z[i]]) ++z[i];
        if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; }
    }
    for (int i = pattern.size() + 1; i < len; ++i)
        if (z[i] == pattern.size()) cout << i - pattern.size() - 1 << ' ';
    return 0;
}

Trie for String Counting

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

struct TrieNode {
    vector<TrieNode*> children;
    int count;
    TrieNode() : children(26, nullptr), count(0) {}
};

class Trie {
    TrieNode* root;
public:
    Trie() { root = new TrieNode(); }
    void insert(const string &s) {
        TrieNode* node = root;
        for (char ch : s) {
            int idx = ch - 'a';
            if (!node->children[idx]) node->children[idx] = new TrieNode();
            node = node->children[idx];
        }
        ++node->count;
    }
    int query(const string &s) {
        TrieNode* node = root;
        for (char ch : s) {
            int idx = ch - 'a';
            if (!node->children[idx]) return 0;
            node = node->children[idx];
        }
        return node->count;
    }
};

int main() {
    int n;
    cin >> n;
    Trie trie;
    while (n--) {
        char op; string s;
        cin >> op >> s;
        if (op == 'I') trie.insert(s);
        else cout << trie.query(s) << endl;
    }
    return 0;
}

Union-Find

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

class UnionFind {
    vector<int> parent;
public:
    UnionFind(int n) : parent(n + 1) { for (int i = 1; i <= n; ++i) parent[i] = i; }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    void unite(int a, int b) { parent[find(a)] = find(b); }
    bool connected(int a, int b) { return find(a) == find(b); }
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    while (m--) {
        char op; int a, b;
        cin >> op >> a >> b;
        if (op == 'M') uf.unite(a, b);
        else cout << (uf.connected(a, b) ? "Yes" : "No") << endl;
    }
    return 0;
}

Basic Algorithms

Quick Sort

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

void quickSort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[(left + right) / 2], i = left - 1, j = right + 1;
    while (i < j) {
        do ++i; while (arr[i] < pivot);
        do --j; while (arr[j] > pivot);
        if (i < j) swap(arr[i], arr[j]);
    }
    quickSort(arr, left, j);
    quickSort(arr, j + 1, right);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;
    quickSort(arr, 0, n - 1);
    for (int x : arr) cout << x << ' ';
    return 0;
}

Merge Sort

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

void mergeSort(vector<int> &arr, int left, int right) {
    if (left >= right) return;
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int idx = 0; idx < k; ++idx) arr[left + idx] = temp[idx];
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;
    mergeSort(arr, 0, n - 1);
    for (int x : arr) cout << x << ' ';
    return 0;
}

Dynamic Programing

0/1 Knapsack

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

int main() {
    int items, capacity;
    cin >> items >> capacity;
    vector<int> dp(capacity + 1, 0);
    while (items--) {
        int weight, value;
        cin >> weight >> value;
        for (int w = capacity; w >= weight; --w)
            dp[w] = max(dp[w], dp[w - weight] + value);
    }
    cout << dp[capacity];
    return 0;
}

Unbounded Knapsack

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

int main() {
    int items, capacity;
    cin >> items >> capacity;
    vector<int> dp(capacity + 1, 0);
    while (items--) {
        int weight, value;
        cin >> weight >> value;
        for (int w = weight; w <= capacity; ++w)
            dp[w] = max(dp[w], dp[w - weight] + value);
    }
    cout << dp[capacity];
    return 0;
}

Bounded Knapsack with Binary Optimization

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

int main() {
    int items, capacity;
    cin >> items >> capacity;
    vector<pair<int, int>> goods;
    while (items--) {
        int weight, value, count;
        cin >> weight >> value >> count;
        for (int k = 1; k <= count; k *= 2) {
            count -= k;
            goods.emplace_back(weight * k, value * k);
        }
        if (count > 0) goods.emplace_back(weight * count, value * count);
    }
    vector<int> dp(capacity + 1, 0);
    for (auto &[w, v] : goods)
        for (int j = capacity; j >= w; --j)
            dp[j] = max(dp[j], dp[j - w] + v);
    cout << dp[capacity];
    return 0;
}

Group Knapsack

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

int main() {
    int capacity, groups;
    cin >> capacity >> groups;
    vector<vector<pair<int, int>>> groupItems(groups + 1);
    for (int g = 1; g <= groups; ++g) {
        int count;
        cin >> count;
        while (count--) {
            int weight, value;
            cin >> weight >> value;
            groupItems[g].emplace_back(weight, value);
        }
    }
    vector<int> dp(capacity + 1, 0);
    for (int g = 1; g <= groups; ++g)
        for (int w = capacity; w >= 0; --w)
            for (auto &[weight, value] : groupItems[g])
                if (w >= weight)
                    dp[w] = max(dp[w], dp[w - weight] + value);
    cout << dp[capacity];
    return 0;
}

Knapsack with Count of Optimal Solutions

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    int items, capacity;
    cin >> items >> capacity;
    vector<int> maxValue(capacity + 1, 0), ways(capacity + 1, 1);
    while (items--) {
        int weight, value;
        cin >> weight >> value;
        for (int w = capacity; w >= weight; --w) {
            int newValue = maxValue[w - weight] + value;
            if (newValue > maxValue[w]) {
                maxValue[w] = newValue;
                ways[w] = ways[w - weight];
            } else if (newValue == maxValue[w])
                ways[w] = (ways[w] + ways[w - weight]) % MOD;
        }
    }
    cout << ways[capacity];
    return 0;
}

Reconstructing Knapsack Solution

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

int main() {
    int items, capacity;
    cin >> items >> capacity;
    vector<int> weight(items + 1), value(items + 1);
    for (int i = 1; i <= items; ++i) cin >> weight[i] >> value[i];
    vector<vector<int>> dp(items + 2, vector<int>(capacity + 1, 0));
    for (int i = items; i >= 1; --i)
        for (int w = 0; w <= capacity; ++w) {
            dp[i][w] = dp[i + 1][w];
            if (w >= weight[i])
                dp[i][w] = max(dp[i][w], dp[i + 1][w - weight[i]] + value[i]);
        }
    vector<int> selection;
    for (int i = 1, w = capacity; i <= items; ++i)
        if (w >= weight[i] && dp[i][w] == dp[i + 1][w - weight[i]] + value[i]) {
            selection.push_back(i);
            w -= weight[i];
        }
    for (int idx : selection) cout << idx << ' ';
    return 0;
}