// Mochila 0/1: cada objeto se toma una vez o ninguna, sin pasar de la capacidad. Pesos enteros
// positivos y valores no negativos.
#pragma once

#include <algorithm>
#include <cstddef>
#include <map>
#include <utility>
#include <vector>

struct Item {
    std::size_t weight;
    long long value;
};

// table[i][c]: el máximo valor con los primeros i objetos y capacidad c.
inline std::vector<std::vector<long long>> knapsack_table(const std::vector<Item>& items, std::size_t capacity) {
    const std::size_t n = items.size();
    std::vector<std::vector<long long>> table(n + 1, std::vector<long long>(capacity + 1, 0));
    for (std::size_t i = 1; i <= n; i++) {
        const Item& item = items[i - 1];
        for (std::size_t c = 0; c <= capacity; c++) {
            table[i][c] = table[i - 1][c];  // sin el objeto
            if (item.weight <= c) {
                table[i][c] = std::max(table[i][c], item.value + table[i - 1][c - item.weight]);
            }
        }
    }
    return table;
}

// Camina hacia atrás: si la casilla es distinta de la de arriba, el objeto i - 1 se usó.
inline std::vector<std::size_t> knapsack_choose(const std::vector<Item>& items,
                                                const std::vector<std::vector<long long>>& table) {
    std::vector<std::size_t> chosen;
    std::size_t c = table[0].size() - 1;
    for (std::size_t i = items.size(); i > 0; i--) {
        if (table[i][c] != table[i - 1][c]) {
            chosen.push_back(i - 1);
            c -= items[i - 1].weight;
        }
    }
    std::reverse(chosen.begin(), chosen.end());
    return chosen;
}

// Una sola fila, con la capacidad de mayor a menor. Invariante, al escribir la casilla c: las
// casillas mayores que c ya tienen este objeto en cuenta y las demás todavía no.
inline long long knapsack_one_row(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> row(capacity + 1, 0);
    for (const Item& item : items) {
        for (std::size_t c = capacity + 1; c-- > item.weight;) {
            row[c] = std::max(row[c], item.value + row[c - item.weight]);
        }
    }
    return row[capacity];
}

// El mismo código, de menor a mayor: la casilla c - weight ya pudo usar este objeto.
inline long long knapsack_one_row_ascending(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> row(capacity + 1, 0);
    for (const Item& item : items) {
        for (std::size_t c = item.weight; c <= capacity; c++) {
            row[c] = std::max(row[c], item.value + row[c - item.weight]);
        }
    }
    return row[capacity];
}

// Mochila sin límite de copias, por su propia recurrencia: el último objeto puesto es alguno.
inline long long unbounded_knapsack(const std::vector<Item>& items, std::size_t capacity) {
    std::vector<long long> best(capacity + 1, 0);
    for (std::size_t c = 1; c <= capacity; c++) {
        for (const Item& item : items) {
            if (item.weight <= c) best[c] = std::max(best[c], item.value + best[c - item.weight]);
        }
    }
    return best[capacity];
}

// Greedy por valor/peso, de mayor a menor, tomando lo que quepa. Se compara sin dividir.
inline long long greedy_by_ratio(std::vector<Item> items, std::size_t capacity) {
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.value * static_cast<long long>(b.weight) > b.value * static_cast<long long>(a.weight);
    });
    long long total = 0;
    for (const Item& item : items) {
        if (item.weight <= capacity) {
            capacity -= item.weight;
            total += item.value;
        }
    }
    return total;
}

inline long long greedy_by_value(std::vector<Item> items, std::size_t capacity) {
    std::stable_sort(items.begin(), items.end(), [](const Item& a, const Item& b) { return a.value > b.value; });
    long long total = 0;
    for (const Item& item : items) {
        if (item.weight <= capacity) {
            capacity -= item.weight;
            total += item.value;
        }
    }
    return total;
}

// Un subproblema al que le falta información: "lo mejor con los primeros i objetos", sin la
// capacidad. Guarda una sola respuesta por i y le agrega el objeto si todavía cabe.
inline long long knapsack_without_capacity(const std::vector<Item>& items, std::size_t capacity) {
    long long best_value = 0;
    std::size_t best_weight = 0;
    for (const Item& item : items) {
        if (best_weight + item.weight <= capacity) {
            best_weight += item.weight;
            best_value += item.value;
        }
    }
    return best_value;
}

// Con memoización solo se calculan los estados a los que la recursión llega.
inline long long knapsack_memo(const std::vector<Item>& items, std::size_t i, std::size_t c,
                               std::map<std::pair<std::size_t, std::size_t>, long long>& memo) {
    if (i == 0) return 0;
    const std::pair<std::size_t, std::size_t> key(i, c);
    const auto found = memo.find(key);
    if (found != memo.end()) return found->second;
    const Item& item = items[i - 1];
    long long result = knapsack_memo(items, i - 1, c, memo);
    if (item.weight <= c) {
        result = std::max(result, item.value + knapsack_memo(items, i - 1, c - item.weight, memo));
    }
    memo[key] = result;
    return result;
}

// Prueba los 2^n subconjuntos. Solo sirve de árbitro con n pequeño.
inline long long knapsack_brute(const std::vector<Item>& items, std::size_t capacity) {
    const std::size_t n = items.size();
    long long best = 0;
    for (unsigned mask = 0; mask < (1U << n); mask++) {
        std::size_t weight = 0;
        long long value = 0;
        for (std::size_t i = 0; i < n; i++) {
            if ((mask >> i) & 1U) {
                weight += items[i].weight;
                value += items[i].value;
            }
        }
        if (weight <= capacity) best = std::max(best, value);
    }
    return best;
}