fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4.  
  5. class kanp{
  6. public:
  7.     ll weight, profit;
  8. };
  9.  
  10. bool cmp(kanp sack1, kanp sack2)
  11. {
  12.     return sack1.profit < sack2.profit;
  13. }
  14.  
  15. ll traditional_kanp_sack(kanp sack[], ll primes[], ll N, ll W)
  16. {
  17.         //dp[N][P][W]
  18.  
  19.         ll ***dp = new ll**[2];
  20.  
  21.         for(ll i = 0; i < 2; i++)
  22.            dp[i] = new ll*[11];
  23.  
  24.         for(ll i = 0; i < 2; i++)
  25.            for(ll j = 0; j < 11; j++)
  26.               dp[i][j] = new ll[W + 1]();
  27.  
  28.         ll n, p, ans1, ans2;
  29.  
  30.         for(ll i = 1; i <= N; i++)
  31.         {
  32.            n = i & 1;
  33.  
  34.            for(ll w = 1; w <= W; w++)
  35.  
  36.            {    
  37.                dp[n][0][w]=dp[n^1][0][w];
  38.                if(w >= sack[i].weight)
  39.                    {
  40.  
  41.                        dp[n][0][w] = max(dp[n^1][0][w], sack[i].profit + dp[n^1][0][w- sack[i].weight]);
  42.                    }
  43.  
  44.                for(ll j = 1; j < 11; j++)
  45.                {
  46.                    p = j;
  47.                    //cout << n << "  " << p << "  " << w << "\n";
  48.  
  49.                    dp[n][p][w] = dp[n ^ 1][p][w];
  50.  
  51.                    ans1 = ans2 = INT_MIN;
  52.  
  53.                    if(w >= sack[i].weight)
  54.                    {
  55.  
  56.                        ans2 = dp[n ^ 1][p - 1][w - sack[i].weight] + (sack[i].profit * primes[p]);
  57.                    }
  58.  
  59.                    ans1 = max(ans1, ans2);
  60.  
  61.                    dp[n][p][w] = max(dp[n][p][w], ans1);
  62.                }
  63.            }
  64.  
  65.         }
  66.  
  67.         ans1 = dp[N & 1][10][W];
  68.  
  69.         for(ll i = 0; i < 2; i++)
  70.           for(ll j = 0; j < 11; j++)
  71.             delete [] dp[i][j];
  72.  
  73.         for(ll i = 0; i < 2; i++)
  74.            delete [] dp[i];
  75.  
  76.            delete [] dp;
  77.  
  78.     return ans1;       
  79. }
  80.  
  81. int main()
  82. {
  83.    ll t;
  84.  
  85.    t = 1;
  86.  
  87.    while(t--)
  88.    {
  89.  
  90.     ll N, W;
  91.  
  92.     cin >> N >> W;
  93.  
  94.     kanp sack[N + 1];
  95.  
  96.     sack[0].weight = sack[0].profit = 0;
  97.  
  98.     for(ll i = 1; i <= N; i++)
  99.         cin >> sack[i].profit >> sack[i].weight;;
  100.  
  101.     sort(sack, sack + (N+1), cmp);
  102.  
  103.     ll primes[11] = {1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
  104.  
  105.     ll value = traditional_kanp_sack(sack, primes, N, W);
  106.  
  107.     cout << value << "\n";
  108.  
  109.   }
  110.  
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0s 4560KB
comments (?)
stdin
copy 
3 4
1 1
2 1
3 1
stdout
copy 
152
https://ideone.com/BPBU3c
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!