// La mochila en su versión de decisión: ¿hay objetos con peso a lo sumo W y valor al menos V? Suma de
// subconjuntos se reduce a ella, y con una caja negra para la decisión se recupera la de optimización.
#pragma once
#include <cstddef>
#include <vector>
#include "subset_sum.h"

struct Item {
    Number weight;
    Number value;
};

struct KnapsackDecision {
    std::vector<Item> items;
    Number capacity;
    Number goal;
};

// Peso y valor iguales al número, y capacidad y meta iguales al objetivo.
inline KnapsackDecision knapsack_from_subset_sum(const std::vector<Number>& numbers, Number target) {
    KnapsackDecision out{{}, target, target};
    for (Number x : numbers) out.items.push_back({x, x});
    return out;
}

// La mejor ganancia con capacidad W, en O(nW), como en la semana 7.
inline Number knapsack_best(const std::vector<Item>& items, Number capacity) {
    std::vector<Number> best(static_cast<std::size_t>(capacity) + 1, 0);
    for (const Item& item : items) {
        for (std::size_t c = static_cast<std::size_t>(capacity) + 1; c-- > static_cast<std::size_t>(item.weight);) {
            best[c] = std::max(best[c], best[c - static_cast<std::size_t>(item.weight)] + item.value);
        }
    }
    return best[static_cast<std::size_t>(capacity)];
}

inline bool knapsack_decide(const KnapsackDecision& d) {
    return knapsack_best(d.items, d.capacity) >= d.goal;
}

// Búsqueda binaria sobre el valor, llamando solo a la decisión. Cuenta las llamadas.
inline Number knapsack_optimum_by_search(const std::vector<Item>& items, Number capacity, int& calls) {
    Number low = 0;
    Number high = 0;
    for (const Item& item : items) high += item.value;
    calls = 0;
    // Invariante: se puede alcanzar low, y no se puede alcanzar nada mayor que high.
    while (low < high) {
        Number middle = low + (high - low + 1) / 2;
        calls++;
        if (knapsack_decide({items, capacity, middle})) low = middle;
        else high = middle - 1;
    }
    return low;
}

// Qué objetos llevar, también solo con la decisión: un objeto sobra si sin él se llega al mismo valor.
inline std::vector<std::size_t> knapsack_items_by_search(const std::vector<Item>& items, Number capacity) {
    int calls = 0;
    const Number goal = knapsack_optimum_by_search(items, capacity, calls);
    std::vector<Item> kept = items;
    std::vector<std::size_t> chosen;
    Number used_value = 0;
    Number room = capacity;
    for (std::size_t i = 0; i < items.size(); i++) {
        Item current = kept[i];
        kept[i] = {0, 0};
        if (!knapsack_decide({kept, room, goal - used_value})) {
            chosen.push_back(i);
            used_value += current.value;
            room -= current.weight;
        }
    }
    return chosen;
}