NickAndNick

Задача о рюкзаке

Sep 27th, 2019
114
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <list>
  4. using namespace std;
  5. struct Thing {
  6.     double cost;
  7.     double weight;
  8.     Thing(double cost, double weight) : cost(cost), weight(weight) { }
  9.     friend bool operator==(const Thing& a, const Thing& b) {
  10.         return a.cost == b.cost && a.weight == b.weight;
  11.     }
  12. };
  13. class Backpack {
  14. public:
  15.     Backpack(double limit) : limit_(limit), best_(0) { }
  16.     list<Thing> enumeration(list<Thing>& things) {
  17.         if (things.size() > 0) check(things);
  18.         for (auto& thing : things) {
  19.             auto tmp = list<Thing>(things);
  20.             tmp.remove(thing);
  21.             enumeration(tmp);
  22.         }
  23.         return things_;
  24.     }
  25. private:
  26.     double limit_;
  27.     double best_;
  28.     list<Thing> things_;
  29.     double weight_(list<Thing>& things)const {
  30.         auto sum = 0.0;
  31.         for (auto& thing : things) sum += thing.weight;
  32.         return sum;
  33.     }
  34.     double cost_(list<Thing>& things)const {
  35.         auto sum = 0.0;
  36.         for (auto& thing : things) sum += thing.cost;
  37.         return sum;
  38.     }
  39.     void check(list<Thing>& things) {
  40.         if (0 == things_.size()) {
  41.             if (weight_(things) <= limit_) {
  42.                 things_ = things;
  43.                 best_ = cost_(things);
  44.             }
  45.         }
  46.         else {
  47.             if (weight_(things) <= limit_ && cost_(things) > best_) {
  48.                 things_ = things;
  49.                 best_ = cost_(things);
  50.             }
  51.         }
  52.     }
  53. };
  54. list<Thing> input(unsigned quantity) {
  55.     list<Thing> things;
  56.     for (auto i = 0U; i < quantity; ++i) {
  57.         cout << "Цена " << i + 1 << " предмета: ";
  58.         double cost;
  59.         cin >> cost;
  60.         cout << "Вес " << i + 1 << " предмета: ";
  61.         double weight;
  62.         cin >> weight;
  63.         things.emplace_back(Thing(cost, weight));
  64.     }
  65.     return things;
  66. }
  67. void show(list<Thing>& things) {
  68.     auto weight = 0.0;
  69.     auto cost = 0.0;
  70.     for (auto& thing : things) {
  71.         weight += thing.weight;
  72.         cost += thing.cost;
  73.         cout
  74.             << "Вес: " << thing.weight
  75.             << ", цена: " << thing.cost << '\n';
  76.     }
  77.     cout << "Общий вес: " << weight << ", сумма: " << cost << '\n';
  78. }
  79. int main() {
  80.     setlocale(LC_CTYPE, "Russian");
  81.     cout << "Введите предельный вес рюкзака: ";
  82.     double weight;
  83.     cin >> weight;
  84.     Backpack backpack(weight);
  85.     cout << "Введите количество предметов: ";
  86.     unsigned quantity;
  87.     cin >> quantity;
  88.     auto things = input(quantity);
  89.     auto result = backpack.enumeration(things);
  90.     show(result);
  91.     system("pause");
  92. }
RAW Paste Data