fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define maxn 1000005
  4. #define endl "\n"
  5. using namespace std;
  6.  
  7. int n, w, a[105], c[105],  b[105], ress = INT_MIN;
  8. vector<vector<int>>kq;
  9. void backtrack(int i, int sum, int ans, vector<int>res){
  10.     if(i == n + 1){
  11.         if(ans > ress){
  12.             ress = ans;
  13.             kq.push_back(res); 
  14.         }
  15.         return;
  16.     }
  17.     //chọn ai
  18.     if(sum + a[i] <= w){
  19.         res.push_back(1);
  20.         backtrack(i + 1, sum + a[i], ans + c[i], res);
  21.         res.pop_back();
  22.     }
  23.     //không chọn ai
  24.     if(sum <= w){
  25.         res.push_back(0);
  26.         backtrack(i + 1, sum, ans, res);
  27.         res.pop_back();
  28.     }
  29. }
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  33.     cin >> n >> w; 
  34.     for(int i = 1; i <= n; ++i) cin >> c[i];
  35.     for(int i = 1; i <= n; ++i) cin >> a[i];
  36.     backtrack(1, 0, 0, {});
  37.     cout << ress << endl;
  38.     for(auto x : kq[kq.size() - 1])
  39.         cout << x << " ";
  40.     return 0;
  41. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
4 10                               
6 5 3 7
5 4 6 5
stdout 
13
1 0 0 1
https://ideone.com/5w1nHc
language:
C++ (gcc 8.3)
created:
243 days 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!