Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <unordered_map>
- #include <fstream>
- #include <stdio.h>
- #include <vector>
- #include <numeric>
- #include <algorithm>
- void processInput(std::ifstream& in, int items, std::vector<int>& values, std::vector<int>& weights) {
- std::string in_line;
- values.resize(items);
- weights.resize(items);
- int i = 0;
- while (std::getline(in, in_line)) {
- sscanf(in_line.data(), "%d%d", &values[i], &weights[i]);
- i += 1;
- }
- }
- void processInput(std::istream& in, int items, std::vector<int>& values, std::vector<int>& weights) {
- std::string in_line;
- values.resize(items);
- weights.resize(items);
- int i = 0;
- while (std::getline(in, in_line)) {
- sscanf(in_line.data(), "%d%d", &values[i], &weights[i]);
- i += 1;
- }
- }
- std::string stringifyAnswer(int value, std::vector<int>& taken) {
- std::string out = std::to_string(value) + '\n';
- for (auto& el : taken) {
- out += std::to_string(el) + ' ';
- }
- return out;
- }
- int ruckzackk(int capacity, int items, std::vector<int>& w, std::vector<int>& v) {
- std::vector<std::vector<int>> m(items, std::vector<int>(capacity, 0));
- for (int i = 1; i < items; ++i) {
- for (int j = 0; j < capacity; ++j) {
- if (w[i] > j) {
- m[i][j] = m[i - 1][j];
- } else {
- m[i][j] = std::max(m[i-1][j], m[i-1][j-w[i]] + v[i]);
- }
- }
- }
- return 0;
- }
- int solveIt(int capacity, std::vector<int>& values, std::vector<int>& weights, std::vector<int>& taken) {
- int CONSTI = 10;
- int items = values.size();
- std::vector<size_t> idx(items);
- std::iota(idx.begin(), idx.end(), 0);
- std::sort(idx.begin(), idx.end(),
- [&](size_t i1, size_t i2) {return (static_cast<double>(values[i1]) / weights[i1]) > (static_cast<double>(values[i2]) / weights[i2]);});
- int value = 0;
- int weight = 0;
- int j = 0;
- for(auto& ind : idx) {
- // std::cerr<<(static_cast<double>(values[el]) / weights[el])<<" ";
- if (weight + weights[ind] > capacity) {
- auto cur_capacity = capacity - weight;
- std::vector<int> ind_to_del;
- std::vector<int> w;
- std::vector<int> v;
- for (int i = 0; i < CONSTI; ++i) {
- ind_to_del.push_back(taken.back());
- auto index = ind_to_del.back();
- w.push_back(weights[index]);
- v.push_back(values[index]);
- taken.pop_back();
- cur_capacity -= w.back();
- value -= v.back();
- weight -= w.back();
- }
- for (int i = j; i < CONSTI + j && i < idx.size(); ++i) {
- ind_to_del.push_back(idx[j] + 1);
- auto index = idx[j];
- w.push_back(weights[index]);
- v.push_back(values[index]);
- }
- ruckzackk(v.size(), cur_capacity, w, v);//best indexes; new value
- }
- weight += weights[ind];
- value += values[ind];
- taken.push_back(ind + 1);
- j += 1;
- }
- std::cerr<<value<<" " << weight<<'\n';
- return value;
- }
- int main(int argc, char* argv[]) {
- int items;
- int capacity;
- std::vector<int> values;
- std::vector<int> weights;
- std::vector<int> taken;
- if (argc != 2) {
- std::cerr << "Not correct number of files" << '\n';
- std::cerr << "seems to be fucking ya contest" << '\n';
- std::string in_line;
- std::getline(std::cin, in_line);
- sscanf(in_line.data(), "%d%d", &items, &capacity);
- processInput(std::cin, items, values, weights);
- } else {
- std::string InputFile(argv[1]);
- std::ifstream Input(InputFile, std::ios::in);
- if (!Input.is_open()) {
- std::cerr << "failed to open " << InputFile << '\n';
- return 1;
- }
- std::string in_line;
- std::getline(Input, in_line);
- sscanf(in_line.data(), "%d%d", &items, &capacity);
- processInput(Input, items, values, weights);
- }
- auto value = solveIt(capacity, values, weights, taken);
- std::cout<<stringifyAnswer(value, taken)<<'\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement