fork download
copy 
  1. // make TARGET sum with K element from array of N
  2. /*
  3. 1 <= n <= 200; 
  4. -1000 <= target <= 1000; 
  5. 0 <= choose <= min(n, 200); 
  6. -100 <= a[i] <= 100
  7. */
  8. #include <bits/stdc++.h>
  9. #define up(i,a,b) for (int i = (int)a; i <= (int)b; i++)
  10. using namespace std;
  11.  
  12. int n;
  13. int a[201];
  14. int target, choose;
  15.  
  16. int offset;
  17.  
  18. int sum_pos, sum_neg;
  19. int dp[2][201*201][201]; //dp[i][j][k] = dung den so thu i, tao thanh tong j, da dung duoc k so
  20.  
  21. void solve(){
  22.     dp[0][offset][0] = -1;
  23.  
  24.     for (int i = 1; i <= n; i++){
  25.         for (int j = sum_neg; j <= sum_pos; j++){
  26.             for (int k = 0; k <= i; k++){
  27.                 dp[(i & 1)][j + offset][k] = dp[(i-1) & 1][j + offset][k];
  28.                 if (k == 0) continue;
  29.                 if (j - a[i] >= sum_neg && j - a[i] <= sum_pos){
  30.                     if (dp[(i-1) & 1][j - a[i] + offset][k-1] != 0){ //chon a[i] ?
  31.                         if (dp[(i & 1)][j + offset][k] == 0){
  32.                             dp[(i & 1)][j + offset][k] = i;
  33.                         }
  34.                     }
  35.                 }
  36.             }
  37.         }
  38.     }
  39. }
  40.  
  41. void trace(int target, int last, int choose){
  42.     vector<int> path;
  43.     while (choose != 0){
  44.         int x = dp[(last & 1)][target + offset][choose];
  45.         target -= a[x];
  46.         path.push_back(x);
  47.         last = (x & 1);
  48.         --choose;
  49.     }
  50.     for (auto x : path) cout << a[x] << " ";
  51.     cout << "\n";
  52. }
  53.  
  54. signed main(){
  55.     ios_base::sync_with_stdio(false);
  56.     cin.tie(0);
  57.     #define Task "A"
  58.     if (fopen(Task".inp", "r")){
  59.         freopen(Task".inp", "r", stdin);
  60.         freopen(Task".out", "w", stdout);
  61.     }
  62.  
  63.     cin >> n >> target >> choose;
  64.     up(i,1,n){
  65.         cin >> a[i];
  66.         if (a[i] < 0) sum_neg += a[i];
  67.         else sum_pos += a[i];
  68.     }
  69.     offset = -sum_neg;
  70.  
  71.     solve();
  72.  
  73.     if (dp[(n & 1)][target + offset][choose] != 0){
  74.         trace(target, dp[(n & 1)][target + offset][choose], choose);
  75.     }
  76. }
  77.  
Success #stdin #stdout 0.02s 10456KB
comments (?)
stdin
copy 
49 107 23
-10 -91 -31 88 -78 -16 -84 -86 78 -37 -48 -65 -72 -22 79 0 65 71 -14 45 63 -3 -36 93 55 18 57 -61 81 86 -20 -36 -63 -20 -79 -98 -6 -64 -35 39 -80 22 66 -3 -27 -42 87 -79 -68
stdout
copy 
55 93 -36 -3 63 45 -14 71 65 0 79 -22 -65 -48 -37 78 -86 -84 -16 -78 88 -31 -10
https://ideone.com/30ykwk
Tạo tổng TARGET từ CHOOSE phần tử trong mảng gồm N phần tủ
language:
C++14 (gcc 8.3)
created:
1 year 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!