SHARE
TWEET

Untitled

a guest May 19th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "ReadWriter.h"
  2. //vector, string, iostream included in "ReadWriter.h"
  3.  
  4. using namespace std;
  5.  
  6. //Можно добавлять любые вспомогательные методы и классы для решения задачи.
  7.  
  8. vector<vector<int>> dinamicArray;
  9.  
  10. /**
  11.  * Метод, который определяет камни, которые нужно взять, по массиву для предподсчета.
  12.  * @param i - текущая строка.
  13.  * @param j - текущий столбец.
  14.  * @param stones - массив камней.
  15.  * @param res - результат (камни, которые мы взяли).
  16.  */
  17. void findWay(int i, int j, int *stones, vector<int> &res) {
  18.     if (dinamicArray[i][j] == 0)
  19.         return;
  20.  
  21.     if (dinamicArray[i][j] != dinamicArray[i - 1][j]) {
  22.         findWay(i - 1, j - stones[i - 1], stones, res);
  23.         res.push_back(stones[i - 1]);
  24.         return;
  25.     }
  26.  
  27.     findWay(i - 1, j, stones, res);
  28.    
  29.     return;
  30. }
  31.  
  32. //Задача реализовать этот метод
  33. //param N - количество камней
  34. //param W - ограничения на вес
  35. //param stones - массив размера N, с весами камней
  36. //param res - вектор результатов (вес камней, которые надо взять)
  37. void solve(int N, int W, int *stones, vector<int> &res) {
  38.     //Задача решается как рюкзак только без ценности предметов (ну... у булыжников же нет особой ценности)
  39.  
  40.     //Массив для предподсчета.
  41.     dinamicArray = vector<vector<int>>(N + 1);
  42.  
  43.     //Обнуляем левый бортик.
  44.     for (int i = 0; i < N + 1; ++i)
  45.         dinamicArray[i] = vector<int>(W + 1, 0);
  46.  
  47.     //Обнуляем верхний бортик.
  48.     for (int j = 0; j < W + 1; ++j)
  49.         dinamicArray[0][j] = 0;
  50.  
  51.     //Решаем задачу.
  52.     for (int i = 1; i < N + 1; ++i)
  53.         for (int j = 1; j < W + 1; ++j)
  54.             if (j - stones[i - 1] >= 0)
  55.                 dinamicArray[i][j] = max(dinamicArray[i - 1][j],
  56.                                          dinamicArray[i - 1][j - stones[i - 1]] + stones[i - 1]);
  57.             else
  58.                 dinamicArray[i][j] = dinamicArray[i - 1][j];
  59.  
  60.     //Восстанавливаем путь.        
  61.     findWay(N, W, stones, res);
  62.  
  63.     return;
  64. }
  65.  
  66. int main(int argc, const char *argv[]) {
  67.     ReadWriter rw;
  68.     int N = rw.readInt(); //камни
  69.     int W = rw.readInt(); //ограничения на вес
  70.     int *arr = new int[N]; //имеющиеся камни
  71.     rw.readArr(arr, N);
  72.  
  73.     //основной структурой выбран вектор, так как заранее неизвестно какое количество камней будет взято
  74.     vector<int> res;
  75.     //решаем задачу
  76.     solve(N, W, arr, res);
  77.     int sum = 0;
  78.     for (int i = 0; i < res.size(); i++)
  79.         sum += res.at(i);
  80.  
  81.     //записываем ответ в файл
  82.     rw.writeInt(sum); //итоговый вес
  83.     rw.writeInt(res.size()); //количество взятых камней
  84.     rw.writeVector(res); //сами камни
  85.  
  86.     delete[] arr;
  87.     return 0;
  88. }
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