# 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.
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. }