Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement