Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.79 KB | None | 0 0
  1. #include <iostream>
  2.  
  3. #include <unordered_map>
  4. #include <fstream>
  5. #include <stdio.h>
  6. #include <vector>
  7. #include <numeric>
  8. #include <algorithm>
  9. void processInput(std::ifstream& in, int items, std::vector<int>& values, std::vector<int>& weights) {
  10.     std::string in_line;
  11.     values.resize(items);
  12.     weights.resize(items);
  13.     int i = 0;
  14.     while (std::getline(in, in_line)) {
  15.         sscanf(in_line.data(), "%d%d", &values[i], &weights[i]);
  16.         i += 1;
  17.     }
  18. }
  19. void processInput(std::istream& in, int items, std::vector<int>& values, std::vector<int>& weights) {
  20.     std::string in_line;
  21.     values.resize(items);
  22.     weights.resize(items);
  23.     int i = 0;
  24.     while (std::getline(in, in_line)) {
  25.         sscanf(in_line.data(), "%d%d", &values[i], &weights[i]);
  26.         i += 1;
  27.     }
  28. }
  29. std::string stringifyAnswer(int value, std::vector<int>& taken) {
  30.     std::string out = std::to_string(value) + '\n';
  31.     for (auto& el : taken) {
  32.         out += std::to_string(el) + ' ';
  33.     }
  34.     return out;
  35. }
  36. int ruckzackk(int capacity, int items, std::vector<int>& w, std::vector<int>& v) {
  37.     std::vector<std::vector<int>> m(items, std::vector<int>(capacity, 0));
  38.     for (int i = 1; i < items; ++i) {
  39.         for (int j = 0; j < capacity; ++j) {
  40.             if (w[i] > j) {
  41.                 m[i][j] = m[i - 1][j];
  42.             } else {
  43.                 m[i][j] = std::max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
  44.             }
  45.         }
  46.     }
  47.     return 0;
  48. }
  49. int solveIt(int capacity, std::vector<int>& values, std::vector<int>& weights, std::vector<int>& taken) {
  50.     int CONSTI = 10;
  51.     int items = values.size();
  52.     std::vector<size_t> idx(items);
  53.     std::iota(idx.begin(), idx.end(), 0);
  54.     std::sort(idx.begin(), idx.end(),
  55.        [&](size_t i1, size_t i2) {return (static_cast<double>(values[i1]) /  weights[i1]) > (static_cast<double>(values[i2]) /  weights[i2]);});
  56.     int value = 0;
  57.     int weight = 0;
  58.     int j = 0;
  59.     for(auto& ind : idx) {
  60.         // std::cerr<<(static_cast<double>(values[el]) /  weights[el])<<" ";
  61.         if (weight + weights[ind] > capacity) {
  62.             auto cur_capacity = capacity - weight;
  63.             std::vector<int> ind_to_del;
  64.             std::vector<int> w;
  65.             std::vector<int> v;
  66.             for (int i = 0; i < CONSTI; ++i) {
  67.                 ind_to_del.push_back(taken.back());
  68.                 auto index = ind_to_del.back();
  69.                 w.push_back(weights[index]);
  70.                 v.push_back(values[index]);
  71.                 taken.pop_back();
  72.                 cur_capacity -= w.back();
  73.                 value -= v.back();
  74.                 weight -= w.back();
  75.             }
  76.             for (int i = j; i < CONSTI + j && i < idx.size(); ++i) {
  77.                 ind_to_del.push_back(idx[j] + 1);
  78.                 auto index = idx[j];
  79.                 w.push_back(weights[index]);
  80.                 v.push_back(values[index]);
  81.             }
  82.             ruckzackk(v.size(), cur_capacity, w, v);//best indexes; new value
  83.  
  84.         }
  85.         weight += weights[ind];
  86.         value += values[ind];
  87.         taken.push_back(ind + 1);
  88.         j += 1;
  89.     }
  90.     std::cerr<<value<<" " << weight<<'\n';
  91.     return value;
  92. }
  93. int main(int argc, char* argv[]) {
  94.     int items;
  95.     int capacity;
  96.     std::vector<int> values;
  97.     std::vector<int> weights;
  98.     std::vector<int> taken;
  99.     if (argc != 2) {
  100.         std::cerr << "Not correct number of files" << '\n';
  101.         std::cerr << "seems to be fucking ya contest" << '\n';
  102.         std::string in_line;
  103.         std::getline(std::cin, in_line);
  104.         sscanf(in_line.data(), "%d%d", &items, &capacity);
  105.  
  106.         processInput(std::cin, items, values, weights);
  107.     } else {
  108.         std::string InputFile(argv[1]);
  109.         std::ifstream Input(InputFile, std::ios::in);
  110.         if (!Input.is_open()) {
  111.             std::cerr << "failed to open " << InputFile << '\n';
  112.             return 1;
  113.         }
  114.         std::string in_line;
  115.         std::getline(Input, in_line);
  116.         sscanf(in_line.data(), "%d%d", &items, &capacity);
  117.         processInput(Input, items, values, weights);
  118.     }
  119.     auto value = solveIt(capacity, values, weights, taken);
  120.  
  121.     std::cout<<stringifyAnswer(value, taken)<<'\n';
  122.     return 0;
  123. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement