// Mochila: los greedy que fallan, la tabla completa y la reconstrucción.
#include <iomanip>
#include <iostream>
#include <map>
#include <vector>

#include "knapsack.h"

namespace {

void print_items(const std::vector<Item>& items, std::size_t capacity) {
    std::cout << "  capacidad " << capacity << ", objetos (peso, valor):";
    for (const Item& item : items) std::cout << " (" << item.weight << ", " << item.value << ")";
    std::cout << '\n';
}

void compare(const char* title, const std::vector<Item>& items, std::size_t capacity) {
    std::cout << title << ":\n";
    print_items(items, capacity);
    std::cout << "  óptimo por fuerza bruta: " << knapsack_brute(items, capacity) << '\n';
    std::cout << "  mayor valor/peso:        " << greedy_by_ratio(items, capacity) << '\n';
    std::cout << "  mayor valor:             " << greedy_by_value(items, capacity) << '\n';
    std::cout << "  sin capacidad en el subproblema: " << knapsack_without_capacity(items, capacity) << '\n';
    std::cout << "  tabla:                   " << knapsack_table(items, capacity).back()[capacity] << "\n\n";
}

}  // namespace

int main() {
    const std::vector<Item> items = {{2, 3}, {3, 4}, {4, 5}, {5, 8}};
    const std::size_t capacity = 9;
    compare("El ejemplo de la tabla", items, capacity);
    compare("Un objeto valioso que no deja sitio", {{6, 30}, {5, 20}, {5, 20}}, 10);

    const std::vector<std::vector<long long>> table = knapsack_table(items, capacity);
    std::cout << "        c:";
    for (std::size_t c = 0; c <= capacity; c++) std::cout << std::setw(3) << c;
    std::cout << '\n';
    for (std::size_t i = 0; i <= items.size(); i++) {
        if (i == 0) {
            std::cout << "ninguno  ";
        } else {
            std::cout << "(" << items[i - 1].weight << ", " << items[i - 1].value << ")   ";
        }
        std::cout << " ";
        for (std::size_t c = 0; c <= capacity; c++) std::cout << std::setw(3) << table[i][c];
        std::cout << '\n';
    }

    std::cout << "\nHacia atrás:\n";
    std::size_t c = capacity;
    for (std::size_t i = items.size(); i > 0; i--) {
        const long long here = table[i][c];
        const long long above = table[i - 1][c];
        if (here != above) {
            std::cout << "  T[" << i << "][" << c << "] = " << here << " != T[" << i - 1 << "][" << c << "] = " << above
                      << ": se toma (" << items[i - 1].weight << ", " << items[i - 1].value << "), c = " << c << " - "
                      << items[i - 1].weight << '\n';
            c -= items[i - 1].weight;
        } else {
            std::cout << "  T[" << i << "][" << c << "] = " << here << " = T[" << i - 1 << "][" << c << "]: no hace falta ("
                      << items[i - 1].weight << ", " << items[i - 1].value << ")\n";
        }
    }

    std::map<std::pair<std::size_t, std::size_t>, long long> memo;
    const long long memo_value = knapsack_memo(items, items.size(), capacity, memo);
    std::cout << "\nCon memoización: valor " << memo_value << ", " << memo.size() << " estados calculados";
    std::cout << " de " << items.size() * (capacity + 1) << " casillas con i >= 1\n";
}