Advertisement
Guest User

Untitled

a guest
Oct 16th, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. int st[100], n, L;
  7. int bara[100];
  8. int este = 0, s=0;
  9.  
  10. int surjectiva(int k)
  11. {
  12.     bool ok;
  13.     for(int i = 1; i <= n; i++)
  14.     {
  15.         ok = false;
  16.         for(int j = 1; j <= k; j++)
  17.             if(bara[i] == bara[st[j]])
  18.                 ok = true;
  19.         if(!ok)
  20.             return 0;
  21.     }
  22.     return 1;
  23. }
  24.  
  25. void citire()
  26. {
  27.     ifstream f("bara.in");
  28.     f >> L >> n;
  29.     for(int i = 1; i <= n; i++)
  30.         f >> bara[i];
  31.     f.close();
  32. }
  33.  
  34. void init(int k)
  35. {
  36.     if(k == 1)
  37.         st[k] = 0;
  38.     else
  39.         st[k] = st[k-1] - 1;
  40. }
  41.  
  42. int succesor(int k)
  43. {
  44.     if(st[k] < n)
  45.     {
  46.         st[k]++;
  47.         return 1;
  48.     }
  49.     else
  50.     {
  51.         s -= bara[st[k-1]];
  52.         return 0;
  53.     }
  54. }
  55.  
  56. int valid(int k)
  57. {
  58.     if(s + bara[st[k]] <= L)
  59.     {
  60.         s += bara[st[k]];
  61.         return 1;
  62.     }
  63.     return 0;
  64. }
  65.  
  66. int solutie(int k)
  67. {
  68.     return s == L;
  69. }
  70.  
  71. void tipar(int k)
  72. {
  73.     este = 1;
  74.     for(int i = 1; i <= k; i++)
  75.         cout << bara[st[i]] << " ";
  76.     cout << "\n";
  77.     s -= bara[st[k]];
  78. }
  79.  
  80. void bkt(int k)
  81. {
  82.     init(k);
  83.     while(succesor(k))
  84.     {
  85.         if(valid(k))
  86.         {
  87.             if(solutie(k) && surjectiva(k))
  88.             {
  89.                 tipar(k);
  90.             }
  91.             else
  92.             {
  93.                 bkt(k+1);
  94.             }
  95.         }
  96.     }
  97. }
  98.  
  99. int main()
  100. {
  101.     citire();
  102.     bkt(1);
  103.     if(!este)
  104.         cout << "Imposibil";
  105.     return 0;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement