SHARE
TWEET

Untitled

AdrianMadajewski May 28th, 2020 917 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>    // for std::sort
  4.  
  5. struct Item {
  6.     int id;
  7.     int value;
  8.     int weight;
  9.  
  10.     Item(int id, int _value, int _weight) : id(id), value(_value), weight(_weight) {};
  11.     Item() = default;
  12. };
  13.  
  14. int getUserInput(const std::string& message) {
  15.     if (!message.empty())
  16.         std::cout << message << '\n';
  17.  
  18.     while (true) {
  19.         int x{};
  20.         std::cin >> x;
  21.  
  22.         if (std::cin.fail()) {
  23.             std::cin.clear();
  24.             std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  25.             std::cerr << "Invalid input - please try again." << '\n';
  26.         }
  27.         else {
  28.             std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
  29.  
  30. if (x <= 0) {
  31.     std::cerr << "Invalid input - must be greater than 0" << '\n';
  32.     std::cout << message << '\n';
  33. }
  34. else {
  35.     return x;
  36. }
  37.  
  38.         }
  39.     }
  40. }
  41.  
  42. std::vector<Item> getItemsFromUser(int numberOfItems) {
  43.  
  44.     std::cout << "Enter items: " << '\n';
  45.     std::vector<Item> loadedItems;
  46.  
  47.     for (int i = 0; i < numberOfItems; ++i) {
  48.         std::cout << "Item index: " << i + 1 << " -> weight = ";
  49.         int weight = getUserInput("");
  50.  
  51.         std::cout << "Item index: " << i + 1 << " -> value  = ";
  52.         int value = getUserInput("");
  53.  
  54.         Item it(i, value, weight);
  55.         loadedItems.emplace_back(it);
  56.     }
  57.  
  58.     return loadedItems;
  59. }
  60.  
  61. bool compareByMassUnit(Item first, Item second) {
  62.     double worthFirst = static_cast<double>(first.value) / first.weight;
  63.     double worthSecond = static_cast<double>(second.value) / second.weight;
  64.     return worthFirst > worthSecond;
  65. }
  66.  
  67. void knapsackGreedy(std::vector<Item> items, int knapsackCapacity) {
  68.     int numberOfItems = items.size();
  69.  
  70.     std::vector<int> resultsX;
  71.  
  72.     // Sort items in descending order
  73.     std::sort(items.begin(), items.end(), compareByMassUnit);
  74.  
  75.     int currentWeight = 0;
  76.     int bestValue = 0;
  77.  
  78.     for (int i = 0; i < numberOfItems; ++i) {
  79.         if (currentWeight + items[i].weight <= knapsackCapacity) {
  80.             currentWeight += items[i].weight;
  81.             bestValue += items[i].value;
  82.             resultsX.push_back(items[i].id);
  83.         }
  84.     }
  85.  
  86.     // SHOULD BE FUNCTION
  87.     std::cout << "Maximum value = " << bestValue << '\n';
  88.     std::cout << "Weight: " << currentWeight << '\n';
  89.     std::cout << "Inside backpack: ";
  90.     for (const auto& id : resultsX) {
  91.         std::cout << id + 1 << ' ';
  92.     }
  93.     std::cout << '\n';
  94. }
  95.  
  96. // CHANGE THE INT TO GREATER VALUES
  97. void knapsackBrute(std::vector<Item> items, int knapsackCapacity) {
  98.     int numberOfItems = items.size();
  99.     int fmax = 0;
  100.     int wmax = 0;
  101.     int solution = 0;
  102.  
  103.     std::vector<int> resultsX;
  104.  
  105.     int permutations = static_cast<int>(std::pow(2, numberOfItems));
  106.     for (int X = 1; X < permutations; ++X) {
  107.  
  108.         int weightX = 0;
  109.         int valueX = 0;
  110.  
  111.         for (int itemIndex = 0; itemIndex < numberOfItems; ++itemIndex) {
  112.             if (((X >> itemIndex) & 1) != 1) {
  113.                 continue;
  114.             }
  115.  
  116.             weightX += items[itemIndex].weight;
  117.             valueX += items[itemIndex].value;
  118.         }
  119.  
  120.         if (weightX <= knapsackCapacity && valueX >= fmax) {
  121.             fmax = valueX;
  122.             wmax = weightX;
  123.             solution = X;
  124.         }
  125.     }
  126.  
  127.     for (int itemIndex = 0; itemIndex < numberOfItems; ++itemIndex) {
  128.         if (((solution >> itemIndex) & 1) == 1) {
  129.             resultsX.push_back(itemIndex + 1);
  130.         }
  131.     }
  132.  
  133.     // SHOULD BE FUNCTION
  134.     std::cout << "Maximum value = " << fmax << '\n';
  135.     std::cout << "Weight: " << wmax << '\n';
  136.     std::cout << "Inside backpack: ";
  137.     for (const auto& id : resultsX) {
  138.         std::cout << id << ' ';
  139.     }
  140.     std::cout << '\n';
  141. }
  142.  
  143. int main()
  144. {
  145.     int knapsackCapacity = getUserInput("Enter the knapsack capacity: ");
  146.     int numberOfItems = getUserInput("Enter number of items: ");
  147.  
  148.     auto items = getItemsFromUser(numberOfItems);
  149.  
  150.     std::cout << "-----------KNAPSACK GREEDY----------" << '\n';
  151.     knapsackGreedy(items, knapsackCapacity);
  152.     std::cout << "-------------------------------------" << '\n';
  153.  
  154.     std::cout << "-----------KNAPSACK BRUTE----------" << '\n';
  155.     knapsackBrute(items, knapsackCapacity);
  156.     std::cout << "-------------------------------------" << '\n';
  157.  
  158.  
  159.  
  160.     return 0;
  161. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top