Advertisement
HabKaffee

Greedy algorithm

Oct 31st, 2020
132
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cmath>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <fstream>
  5.  
  6. std::ifstream FileIn("Task.txt");
  7.  
  8.  
  9. void bubbleSortForAlg(double** arr, int n) {
  10.     double temp = 0;  
  11.     for (size_t i = 0; i < n-1; i++) {
  12.         for (size_t j = 0; j < n - i - 1; ++j)
  13.             if (arr[j][2] > arr[j+1][2]) {
  14.                 for (size_t k = 0; k < 3; ++k) {
  15.                     temp = arr[j][k];
  16.                     arr[j][k] = arr[j+1][k];
  17.                     arr[j+1][k] = temp;
  18.                 }
  19.             }
  20.     }
  21.     std::cout << std::endl;
  22. }
  23.  
  24. void printArr(double** array, int numberOfItem) {
  25.     for (size_t i = 0; i < numberOfItem; ++i) {
  26.         for (size_t j = 0; j < 3; ++j) {
  27.             std::cout << array[i][j] << "\t";
  28.         }
  29.         std::cout << std::endl;
  30.     }
  31. }
  32.  
  33. double greedyAlg(double *arrayOfCost, double *arrayOfWeight, int maxWeight, int numberOfItem) {
  34.     double** arrayOfWeightAndUnitValue = new double* [numberOfItem];
  35.     for (size_t i = 0; i < numberOfItem; ++i) {
  36.         arrayOfWeightAndUnitValue[i] = new double[3];
  37.     }
  38.     for (size_t i = 0; i < numberOfItem; ++i) {
  39.         arrayOfWeightAndUnitValue[i][0] = arrayOfWeight[i];
  40.         arrayOfWeightAndUnitValue[i][1] = arrayOfCost[i];
  41.         arrayOfWeightAndUnitValue[i][2] = arrayOfWeightAndUnitValue[i][1]/arrayOfWeightAndUnitValue[i][0];
  42.     }
  43.    
  44.     //printArr(arrayOfWeightAndUnitValue, numberOfItem);
  45.  
  46.     bubbleSortForAlg(arrayOfWeightAndUnitValue, numberOfItem);
  47.  
  48.     //printArr(arrayOfWeightAndUnitValue, numberOfItem);
  49.  
  50.     double curentWeight = 0, maxCost = 0;
  51.     int count = 0;
  52.  
  53.     for (int i = (numberOfItem-1); i >=0; --i) {
  54.         if (arrayOfWeightAndUnitValue[i][0] + curentWeight <= maxWeight) {
  55.             curentWeight += arrayOfWeightAndUnitValue[i][0];
  56.             maxCost += arrayOfWeightAndUnitValue[i][1];
  57.             count++;
  58.         }
  59.         else {
  60.             if (curentWeight + arrayOfWeightAndUnitValue[i][0] > maxWeight && curentWeight < maxWeight) {
  61.                 maxCost += arrayOfWeightAndUnitValue[i][2] * (maxWeight - curentWeight);
  62.                 curentWeight += arrayOfWeightAndUnitValue[i][0] * (maxWeight - curentWeight);
  63.             }
  64.             count++;
  65.         }
  66.     }
  67.  
  68.     std::cout << "It is necessary to pick item with characteristic \nweight cost\n";
  69.     if (count < numberOfItem) {
  70.         for (int i = numberOfItem - 1; i >= count; --i) {
  71.             for (size_t j = 0; j < 2; ++j) {
  72.                 std::cout << arrayOfWeightAndUnitValue[i][j] << "\t";
  73.             }
  74.             std::cout<<std::endl;
  75.         }
  76.     }
  77.     else {
  78.         for (int i = numberOfItem - 1; i >= 0; --i) {
  79.             for (size_t j = 0; j < 2; ++j) {
  80.                 std::cout << arrayOfWeightAndUnitValue[i][j] << "\t";
  81.             }
  82.             std::cout << std::endl;
  83.         }
  84.     }
  85.  
  86.     for (size_t i = 0; i < numberOfItem; ++i) {
  87.             delete[] arrayOfWeightAndUnitValue[i];
  88.     }
  89.     delete[] arrayOfWeightAndUnitValue;
  90.  
  91.     return maxCost;
  92.  
  93. }
  94.  
  95. int main() {
  96.     int maxWeight = 0, numberOfItem = 0;
  97.  
  98.     FileIn >> numberOfItem >> maxWeight;
  99.  
  100.     double* arrayOfWeight = new double[numberOfItem];
  101.     double* arrayOfCost = new double[numberOfItem];
  102.  
  103.     for (size_t i = 0; i < numberOfItem; ++i) {
  104.         FileIn >> arrayOfWeight[i];
  105.     }
  106.     for (size_t i = 0; i < numberOfItem; ++i) {
  107.         FileIn >> arrayOfCost[i];
  108.     }
  109.  
  110.     double resultOfGreedyAlg = greedyAlg(arrayOfCost, arrayOfWeight, maxWeight, numberOfItem);
  111.     std::cout <<"result is " <<resultOfGreedyAlg;
  112.    
  113.     delete[] arrayOfWeight;
  114.     delete[] arrayOfCost;
  115.  
  116.     return 0;
  117. }
Advertisement
RAW Paste Data Copied
Advertisement