fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <memory>
  6. #include <chrono>
  7. using namespace std::chrono;
  8.  
  9. template<int MAX_N>
  10. milliseconds solve(bool showcomb, bool showres);
  11.  
  12. int main()
  13. {
  14.   // 乱数初期設定等の時間と表示時間を無視するために計算中の時間のみ計測する
  15.   // 結果のみ出力する
  16.   auto s = solve<5000>(false, true);
  17.   std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;
  18.  
  19.   s = solve<10000>(false, true);
  20.   std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;
  21.  
  22.   s = solve<15000>(false, true);
  23.   std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;
  24.  
  25.   s = solve<20000>(false, true);
  26.   std::cout << "Elapsed time = " << s.count() << "ms." << std::endl;
  27. }
  28.  
  29. template<int MAX_N>
  30. milliseconds solve(bool showcomb, bool showres)
  31. {
  32.   std::mt19937 engine(system_clock::now().time_since_epoch().count());
  33.   std::uniform_int_distribution<int> dis(1, 9);
  34.  
  35.   constexpr int MAX_W = MAX_N * 2;
  36.   constexpr int W     = MAX_W + 1;
  37.  
  38.   std::vector<int>  dp( (MAX_N + 1)*(MAX_W + 1) );
  39.   std::vector<bool> bp( (MAX_N + 1)*(MAX_W + 1) );
  40.   std::vector<int>  w( (MAX_N + 1) );
  41.   std::vector<int>  v( (MAX_N + 1) );
  42.   std::vector<int>  sel;
  43.  
  44.   for (int i = 1; i < MAX_N + 1; i++) {
  45.     w[i] = dis(engine);
  46.     v[i] = dis(engine);
  47.   }
  48.  
  49.   // ここから時間測定する
  50.   auto p = system_clock::now();
  51.  
  52.   std::fill(bp.begin(),bp.begin()+MAX_W+1,true);
  53.  
  54.   for (int i = 1; i <= MAX_N; i++) {
  55.     for (int j = 1; j <= MAX_W; j++) {
  56.         if ((w[i] <= j)  && (v[i] + dp[(i-1)*W + j - w[i]]) > dp[ (i - 1) * W + j]) {
  57.           dp[i*W + j] = v[i] + dp[(i - 1)*W + j - w[i]];
  58.           bp[i*W + j] = true;
  59.         } else {
  60.           dp[i*W + j] = dp[(i - 1) * W + j];
  61.           bp[i*W + j] = false;
  62.         }
  63.     }
  64.   }
  65.  
  66.   int maxValue = dp[MAX_N*W + MAX_W], maxWeight = 0;
  67.   int wt = MAX_W;
  68.  
  69.   for (int i = MAX_N; i >= 1; i--)
  70.     if (bp[i*W  + wt]) {
  71.       sel.emplace_back(i);
  72.       wt -= w[i];
  73.       maxWeight += w[i];
  74.     }
  75.  
  76.   std::reverse(std::begin(sel), std::end(sel));
  77.  
  78.   // ここまでの経過時間を取得
  79.   auto s = duration_cast<milliseconds>(system_clock::now() - p);
  80.  
  81.   if (showcomb) {
  82.     for (int i = 0; i < static_cast<int>(sel.size()); i++) {
  83.       std::cout << "(" << w[sel[i]] << "," << v[sel[i]] << ")";
  84.       if (!((i + 1) % 10))
  85.         std::cout << std::endl;
  86.     }
  87.     std::cout << std::endl;
  88.   }
  89.  
  90.   if (showres)
  91.     std::cout << "Answer : number = " << MAX_N << ", weight = " << maxWeight << ", value = " << maxValue << std::endl;
  92.  
  93.   return s;
  94. }
  95.  
Runtime error #stdin #stdout #stderr 2.2s 4496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Answer : number = 5000, weight = 10000, value = 17557
Elapsed time = 239ms.
Answer : number = 10000, weight = 20000, value = 34760
Elapsed time = 979ms.
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/SXOjCw
language:
C++14 (gcc 8.3)
created:
10 years 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!