#include <iostream>
#include <vector>
#include <algorithm>    // for std::sort

struct Item {
    int id;
    int value;
    int weight;

    Item(int id, int _value, int _weight) : id(id), value(_value), weight(_weight) {};
    Item() = default;
};

int getUserInput(const std::string& message) {
    if (!message.empty())
        std::cout << message << '\n';

    while (true) {
        int x{};
        std::cin >> x;

        if (std::cin.fail()) {
            std::cin.clear();
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
            std::cerr << "Invalid input - please try again." << '\n';
        }
        else {
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

if (x <= 0) {
    std::cerr << "Invalid input - must be greater than 0" << '\n';
    std::cout << message << '\n';
}
else {
    return x;
}

        }
    }
}

std::vector<Item> getItemsFromUser(int numberOfItems) {

    std::cout << "Enter items: " << '\n';
    std::vector<Item> loadedItems;

    for (int i = 0; i < numberOfItems; ++i) {
        std::cout << "Item index: " << i + 1 << " -> weight = ";
        int weight = getUserInput("");

        std::cout << "Item index: " << i + 1 << " -> value  = ";
        int value = getUserInput("");

        Item it(i, value, weight);
        loadedItems.emplace_back(it);
    }

    return loadedItems;
}

bool compareByMassUnit(Item first, Item second) {
    double worthFirst = static_cast<double>(first.value) / first.weight;
    double worthSecond = static_cast<double>(second.value) / second.weight;
    return worthFirst > worthSecond;
}

void knapsackGreedy(std::vector<Item> items, int knapsackCapacity) {
    int numberOfItems = items.size();

    std::vector<int> resultsX;

    // Sort items in descending order
    std::sort(items.begin(), items.end(), compareByMassUnit);

    int currentWeight = 0;
    int bestValue = 0;

    for (int i = 0; i < numberOfItems; ++i) {
        if (currentWeight + items[i].weight <= knapsackCapacity) {
            currentWeight += items[i].weight;
            bestValue += items[i].value;
            resultsX.push_back(items[i].id);
        }
    }

    // SHOULD BE FUNCTION
    std::cout << "Maximum value = " << bestValue << '\n';
    std::cout << "Weight: " << currentWeight << '\n';
    std::cout << "Inside backpack: ";
    for (const auto& id : resultsX) {
        std::cout << id + 1 << ' ';
    }
    std::cout << '\n';
}

// CHANGE THE INT TO GREATER VALUES
void knapsackBrute(std::vector<Item> items, int knapsackCapacity) {
    int numberOfItems = items.size();
    int fmax = 0;
    int wmax = 0;
    int solution = 0;

    std::vector<int> resultsX;

    int permutations = static_cast<int>(std::pow(2, numberOfItems));
    for (int X = 1; X < permutations; ++X) {

        int weightX = 0;
        int valueX = 0;

        for (int itemIndex = 0; itemIndex < numberOfItems; ++itemIndex) {
            if (((X >> itemIndex) & 1) != 1) {
                continue;
            }

            weightX += items[itemIndex].weight;
            valueX += items[itemIndex].value;
        }

        if (weightX <= knapsackCapacity && valueX >= fmax) {
            fmax = valueX;
            wmax = weightX;
            solution = X;
        }
    }

    for (int itemIndex = 0; itemIndex < numberOfItems; ++itemIndex) {
        if (((solution >> itemIndex) & 1) == 1) {
            resultsX.push_back(itemIndex + 1);
        }
    }

    // SHOULD BE FUNCTION
    std::cout << "Maximum value = " << fmax << '\n';
    std::cout << "Weight: " << wmax << '\n';
    std::cout << "Inside backpack: ";
    for (const auto& id : resultsX) {
        std::cout << id << ' ';
    }
    std::cout << '\n';
}

int main()
{
    int knapsackCapacity = getUserInput("Enter the knapsack capacity: ");
    int numberOfItems = getUserInput("Enter number of items: ");

    auto items = getItemsFromUser(numberOfItems);

    std::cout << "-----------KNAPSACK GREEDY----------" << '\n';
    knapsackGreedy(items, knapsackCapacity);
    std::cout << "-------------------------------------" << '\n';

    std::cout << "-----------KNAPSACK BRUTE----------" << '\n';
    knapsackBrute(items, knapsackCapacity);
    std::cout << "-------------------------------------" << '\n';



    return 0;
}