fork download 
  1. #include <bits/stdc++.h>
  2. #include <ctime>
  3. using namespace std;
  4.  
  5. const int POPULATION_SIZE = 5000; 
  6. const double MUTATION_RATE = 0.4; 
  7.  
  8. int n;
  9. long long x;
  10. vector<long long> w;
  11.  
  12. struct Individual {
  13.     vector<int> chromosome;
  14.     int rides;
  15.     double fitness;
  16. };
  17.  
  18. void evaluate(Individual& ind) {
  19.     int current_rides = 1;
  20.     long long current_weight = 0;
  21.     double sum_squares = 0;
  22.  
  23.     for (int idx : ind.chromosome) {
  24.         if (current_weight + w[idx] <= x) {
  25.             current_weight += w[idx];
  26.         } else {
  27.             sum_squares += pow((double)current_weight / x, 2);
  28.             current_rides++;
  29.             current_weight = w[idx];
  30.         }
  31.     }
  32.  
  33.     sum_squares += pow((double)current_weight / x, 2);
  34.     ind.rides = current_rides;
  35.     ind.fitness = sum_squares / current_rides; 
  36. }
  37.  
  38.  
  39. Individual crossover(const Individual& p1, const Individual& p2) {
  40.     Individual child;
  41.     child.chromosome.assign(n, -1);
  42.     int left = rand() % n;
  43.     int right = rand() % n;
  44.     if (left > right) swap(left, right);
  45.  
  46.     vector<bool> in_child(n, false);
  47.     for (int i = left; i <= right; ++i) {
  48.         child.chromosome[i] = p1.chromosome[i];
  49.         in_child[p1.chromosome[i]] = true;
  50.     }
  51.  
  52.     int curr_p2 = 0;
  53.  
  54.     for (int i = 0; i < n; ++i) {
  55.         if (child.chromosome[i] == -1) {
  56.             while (in_child[p2.chromosome[curr_p2]]) {
  57.                 curr_p2++;
  58.             }
  59.             child.chromosome[i] = p2.chromosome[curr_p2];
  60.             in_child[p2.chromosome[curr_p2]] = true;
  61.         }
  62.     }
  63.  
  64.     return child;
  65. }
  66.  
  67.  
  68. void mutate(Individual& ind) {
  69.     if ((double)rand() / RAND_MAX < MUTATION_RATE) {
  70.         int i = rand() % n;
  71.         int j = rand() % n;
  72.         swap(ind.chromosome[i], ind.chromosome[j]);
  73.     }
  74. }
  75.  
  76. int main() {
  77.     ios_base::sync_with_stdio(false);
  78.     cin.tie(NULL);
  79.     srand(time(NULL));
  80.  
  81.     double start_time = clock(); 
  82.  
  83.     cin >> n >> x;
  84.     w.resize(n);
  85.     for (int i = 0; i < n; ++i) cin >> w[i];
  86.  
  87.     vector<Individual> population(POPULATION_SIZE);
  88.     int best_global_rides = n;
  89.  
  90.     for (int i = 0; i < POPULATION_SIZE; ++i) {
  91.         population[i].chromosome.resize(n);
  92.         iota(population[i].chromosome.begin(), population[i].chromosome.end(), 0);
  93.         random_shuffle(population[i].chromosome.begin(), population[i].chromosome.end());
  94.         evaluate(population[i]);
  95.         best_global_rides = min(best_global_rides, population[i].rides);
  96.     }
  97.  
  98.     while ((double)(clock() - start_time) / CLOCKS_PER_SEC < 0.90) {
  99.         sort(population.begin(), population.end(), [](const Individual& a, const Individual& b) {
  100.             return a.fitness > b.fitness;
  101.         });
  102.  
  103.         vector<Individual> new_population;
  104.  
  105.         int elitism_count = POPULATION_SIZE / 10;
  106.         for (int i = 0; i < elitism_count; ++i) {
  107.             new_population.push_back(population[i]);
  108.         }
  109.  
  110.         while (new_population.size() < POPULATION_SIZE) {
  111.             int p1_idx = rand() % (POPULATION_SIZE / 2);
  112.             int p2_idx = rand() % (POPULATION_SIZE / 2);
  113.  
  114.             Individual child = crossover(population[p1_idx], population[p2_idx]);
  115.             mutate(child);
  116.             evaluate(child);
  117.  
  118.             best_global_rides = min(best_global_rides, child.rides);
  119.             new_population.push_back(child);
  120.         }
  121.  
  122.         population = new_population;
  123.     }
  124.  
  125.     cout << best_global_rides << "\n";
  126.     return 0;
  127. }
Runtime error #stdin #stdout 0.02s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/yLfyaE
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!