fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. int n, a[10], f[10];
  6. vector<bool> dp(10000, false);
  7. int d = 1;
  8.  
  9. void mark(int sum) {
  10.     dp[sum] = true;
  11. }
  12.  
  13. void pr(int sum) {
  14.     cout << d << ": ";
  15.     for (int i = 0; i < n; i++) {
  16.         if (f[i] > 0)
  17.             cout << a[i] << " ";
  18.     }
  19.     cout << " => sum: " << sum << endl;
  20.     d++;
  21. }
  22.  
  23. void binary(int i, int sum) {
  24.     for (int j = 0; j <= 1; j++) {
  25.         f[i] = 0;
  26.         if (j == 1) 
  27.             f[i] = 1;
  28.         sum += f[i] * a[i];
  29.         if (i == n - 1) {
  30.             mark(sum); 
  31.             // đánh dấu m = sum là có thể phân tích thành tổng ai
  32.             pr(sum);
  33.         } else {
  34.             binary(i + 1, sum);
  35.         }
  36.         if (j == 1) sum -= f[i] * a[i];
  37.     }
  38. }
  39.  
  40. int findSmallestMissing() {
  41.     for (int m = 1; m < dp.size(); m++) {
  42.         if (!dp[m]) return m;
  43.     }
  44.     return -1;
  45. }
  46.  
  47. int main() {
  48.     cout << "n: ";
  49.     cin >> n;
  50.  
  51.     cout << "a[]: ";
  52.     for (int i = 0; i < n; i++) {
  53.         cin >> a[i];
  54.     }
  55.  
  56.     binary(0, 0);
  57.  
  58.     int m = findSmallestMissing();
  59.     cout << "min m = " << m << endl;
  60.  
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
5
12 1 2 3 4
stdout
copy 
n: a[]: 1:  => sum: 0
2: 4  => sum: 4
3: 3  => sum: 3
4: 3 4  => sum: 7
5: 2  => sum: 2
6: 2 4  => sum: 6
7: 2 3  => sum: 5
8: 2 3 4  => sum: 9
9: 1  => sum: 1
10: 1 4  => sum: 5
11: 1 3  => sum: 4
12: 1 3 4  => sum: 8
13: 1 2  => sum: 3
14: 1 2 4  => sum: 7
15: 1 2 3  => sum: 6
16: 1 2 3 4  => sum: 10
17: 12  => sum: 12
18: 12 4  => sum: 16
19: 12 3  => sum: 15
20: 12 3 4  => sum: 19
21: 12 2  => sum: 14
22: 12 2 4  => sum: 18
23: 12 2 3  => sum: 17
24: 12 2 3 4  => sum: 21
25: 12 1  => sum: 13
26: 12 1 4  => sum: 17
27: 12 1 3  => sum: 16
28: 12 1 3 4  => sum: 20
29: 12 1 2  => sum: 15
30: 12 1 2 4  => sum: 19
31: 12 1 2 3  => sum: 18
32: 12 1 2 3 4  => sum: 22
min m = 11
https://ideone.com/alyoMS
language:
C++ (gcc 8.3)
created:
1 day 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!