fork download
copy 
  1. // Author: Sahil Yasar
  2. // Tested here:
  3. // https://w...content-available-to-author-only...j.com/problems/LKS/ [0-1 Knapsack v-1]
  4. // https://a...content-available-to-author-only...r.jp/contests/dp/tasks/dp_e [0-1 Knapsack v-2]
  5. // https://l...content-available-to-author-only...u.vn/problem/knapsack3 [0-1 Knapsack v-3]
  6. // https://c...content-available-to-author-only...s.fi/problemset/task/1634 [Unbounded Knapsack]
  7.  
  8. #include <iostream>
  9. #include <cstring>
  10. #include <numeric>
  11. #include <vector>
  12. #include <algorithm>
  13. using namespace std;
  14. #define endl '\n'
  15.  
  16. // Solution for small knapsack capacity
  17. long long knapsack1(int w[], int v[], int& c, int& n){
  18.     long long ans[c+1];
  19.     memset(ans, 0, sizeof(ans));
  20.     for (int i = 0; i < n; ++i)
  21.         // for (int j = w[i]; j <= c; ++j) // Unbounded Knapsack
  22.         for (int j = c; j >= w[i]; --j) // 0-1 Knapsack
  23.             ans[j] = max(ans[j], ans[j-w[i]] + v[i]);
  24.     return ans[c];
  25. }
  26.  
  27. // Solution for small sum of value
  28. long long knapsack2(int w[], int v[], int& c, int& n){
  29.     int sum = accumulate(v, v+n, 0);
  30.     long long ans[sum+1];
  31.     memset(ans, 0x3f, sizeof(ans));
  32.     ans[0] = 0;
  33.     for (int i = 0; i < n; ++i)
  34.         for (int j = sum; j >= v[i]; --j) // 0-1 Knapsack
  35.             ans[j] = min(ans[j], ans[j-v[i]] + w[i]);
  36.     for (int i = sum; i >= 0; --i)
  37.         if (ans[i] <= c)
  38.             return i;
  39.     return 0;
  40. }
  41.  
  42. struct node{
  43.     long long value, weight;
  44.     int mask;
  45.     node(int m, long long v = 0, long long w = 0)
  46.     : mask(m), value(v), weight(w) {}
  47. };
  48.  
  49. void solve(int w[], int v[], long long c, int n, vector<node>& S){
  50.     int lim = 1<<n;
  51.     for (int mask = 0; mask < lim; ++mask){
  52.         long long weight = 0, value = 0;
  53.         for (int i = 0; i < n; ++i)
  54.             if ((mask>>i)&1){
  55.                 weight += w[i];
  56.                 value += v[i];
  57.                 if (weight > c) break;
  58.             }
  59.         if (weight <= c)
  60.             S.push_back(node(mask, value, weight));
  61.     }
  62. }
  63.  
  64. // Solution for small number of element
  65. long long knapsack3(int w[], int v[], long long& c, int& n){
  66.     int m = n/2;
  67.     int wl[m], vl[m], wr[n-m], vr[n-m];
  68.     for (int i = 0; i < m; ++i)
  69.         wl[i] = w[i], vl[i] = v[i];
  70.     for (int i = m; i < n; ++i)
  71.         wr[i-m] = w[i], vr[i-m] = v[i];
  72.  
  73.     vector<node> Sl, Sr;
  74.     solve(wl, vl, c, m, Sl);
  75.     solve(wr, vr, c, n-m, Sr);
  76.     sort(Sr.begin(), Sr.end(), [](node& a, node& b){
  77.         return (a.weight != b.weight)? a.weight < b.weight: a.value < b.value;
  78.     });
  79.     long long maxval[Sr.size()];
  80.     int maxmask[Sr.size()];
  81.     maxval[0] = Sr[0].value;
  82.     maxmask[0] = Sr[0].mask;
  83.     for (int i = 1; i < Sr.size(); ++i){
  84.         maxval[i] = (maxval[i-1] < Sr[i].value)? Sr[i].value: maxval[i-1];
  85.         maxmask[i] = (maxval[i-1] < Sr[i].value)?Sr[i].mask : maxmask[i-1];
  86.     }
  87.  
  88.     long long res = 0, mask = 0;
  89.     for (node& x: Sl){
  90.         int l = 0, r = int(Sr.size())-1, mid;
  91.         while(l+1 < r){
  92.             mid = (l+r)/2;
  93.             if (x.weight + Sr[mid].weight <= c)
  94.                 l = mid;
  95.             else
  96.                 r = mid;
  97.         }
  98.         long long temp = maxval[l] + x.value;
  99.         if (res < temp){
  100.           res = temp;
  101.           mask = x.mask | (maxmask[l] << m);
  102.         }
  103.     }
  104.     return mask;
  105. }
  106.  
  107. int main(){
  108.     ios_base::sync_with_stdio(false);
  109.     cin.tie(NULL);
  110.     cin.exceptions(cin.failbit);
  111.  
  112.     long long n, c, i;
  113.     cin>>n>>c;
  114.     int w[n], v[n];
  115.     for (i = 0; i < n; ++i)
  116.       cin>>w[i]>>v[i];
  117.  
  118.     long long mask = knapsack3(w, v, c, *(new int(n)));
  119.     cout<<__builtin_popcount(mask)<<endl;
  120.     for (i = 0; i < n; ++i)
  121.       if ((mask>>i)&1)
  122.         cout<<i+1<<" ";
  123.     cout<<endl;
  124.  
  125.     return 0;
  126. }
  127.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
15 1912062020
129481303 327366001
277752658 266091717
216589011 139583521
596739855 301088305
554389709 95819059
425836113 1975801
620836023 53732715
410067921 345142297
740980851 698685481
352225311 811461825
251172363 10045828
193423681 173437189
370742511 35715013
891141681 192001440
141978645 110173617
stdout
copy 
5
1 2 8 9 10
https://ideone.com/2LxqbY
language:
C++14 (gcc 8.3)
created:
239 days 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!