// Mide la mochila de una fila con n fijo y W creciente: cada bit más de W duplica el trabajo.
// Se compila con -O2. Se toma el menor de 3 intentos.
#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>

#include "knapsack.h"

int main() {
    const std::size_t n = 200;
    std::cout << "n = " << n << ", pesos al azar entre 1 y W/2, menor de 3 intentos\n";
    std::cout << " bits de W           W    casillas n·W          ms\n";
    double previous = 0;
    for (unsigned bits = 16; bits <= 25; bits++) {
        const std::size_t capacity = std::size_t{1} << (bits - 1);
        std::mt19937 rng(42);
        std::vector<Item> items;
        for (std::size_t i = 0; i < n; i++) {
            items.push_back({1 + rng() % (capacity / 2), static_cast<long long>(1 + rng() % 1000000)});
        }
        double best_ms = 1e18;
        long long answer = 0;
        for (int attempt = 0; attempt < 3; attempt++) {
            const auto begin = std::chrono::steady_clock::now();
            answer = knapsack_one_row(items, capacity);
            const auto end = std::chrono::steady_clock::now();
            best_ms = std::min(best_ms, std::chrono::duration<double, std::milli>(end - begin).count());
        }
        std::cout << std::setw(9) << bits << std::setw(12) << capacity << std::setw(16)
                  << static_cast<unsigned long long>(n) * capacity << std::setw(12) << std::fixed << std::setprecision(1)
                  << best_ms;
        if (previous > 0) std::cout << "   x" << std::setprecision(2) << best_ms / previous;
        std::cout << "   (óptimo " << answer << ")\n";
        previous = best_ms;
    }
}