Advertisement
Guest User

Untitled

a guest
Jan 8th, 2015
340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <list>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector <vector<int> > nList;
  7. int i = 0, x = 0;
  8. void subset_sum_recursive(list<int> numbers, int target, list<int> partial)
  9. {
  10.         int s = 0;
  11.         for (list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
  12.         {
  13.             s += *cit;
  14.         }
  15.         if(s == target)
  16.         {
  17.                 for (list<int>::iterator cit = partial.begin(); cit != partial.end(); cit++)
  18.                 {
  19.                     int val = int(*cit);
  20.                     nList[i].push_back(val);
  21.                 }
  22.                 i++;
  23.         }
  24.         if(s >= target)
  25.             return;
  26.         int n;
  27.         for (list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
  28.         {
  29.             n = *ai;
  30.             list<int> remaining;
  31.             for(list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
  32.             {
  33.                 if(aj == ai)continue;
  34.                 remaining.push_back(*aj);
  35.             }
  36.             list<int> partial_rec=partial;
  37.             partial_rec.push_back(n);
  38.             subset_sum_recursive(remaining,target,partial_rec);
  39.  
  40.         }
  41. }
  42.  
  43. void subset_sum(list<int> numbers,int target)
  44. {
  45.     subset_sum_recursive(numbers,target,list<int>());
  46. }
  47. /* int main()
  48. {
  49.     std::list<int> a;
  50.     a.push_back (3); a.push_back (9); a.push_back (8);
  51.     a.push_back (4);
  52.     a.push_back (5);
  53.     a.push_back (7);
  54.     a.push_back (10);
  55.     int n = 15;
  56.     subset_sum(a, n);
  57.     for(int i = 0, l = 15; i < l;i++)
  58.     {
  59.         for(int x = 0, y = int(nlist[i].size());x < y;x++)
  60.         {
  61.             printf("%d ", nlist[i][x]);
  62.         }
  63.         printf("\n");
  64.     }
  65.     return 0;
  66. } */
  67.  
  68. int main(void)
  69. {
  70.     int t, n, x, y, z;
  71.     scanf("%d", &t);
  72.     for(int rep = 1;rep <= t;rep++)
  73.     {
  74.         int GP, GC, GF;
  75.         scanf("%d%d%d", &GP, &GC, &GF);
  76.         scanf("%d", &n);
  77.         vector<int> nP, nC, nF;
  78.         for(int i = 0;i < n;i++)
  79.         {
  80.             scanf("%d%d%d", &x, &y, &z);
  81.             nP.push_back(x);
  82.             nC.push_back(y);
  83.             nF.push_back(z);
  84.         }
  85.         list<int> newn(nP.begin(), nP.end());
  86.         nList.clear();
  87.         nList.resize(n);
  88.         subset_sum(newn, GP);
  89.         int sumC = 0, sumF = 0;
  90.         bool checked = false;
  91.         for(int i = 0, l = int(nList.size());i < l;i++)
  92.         {
  93.             if(int(nList[i].size()) != 0)
  94.             {
  95.                 for(int j = 0, a = int(nList[i].size());j < a;j++)
  96.                 {
  97.                     sumC += nC[int(find(nP.begin(), nP.end(), nList[i][j]) - nP.begin())];
  98.                     sumF += nF[int(find(nP.begin(), nP.end(), nList[i][j]) - nP.begin())];
  99.                 }
  100.                 if(sumC == GC && sumF == GF)
  101.                 {
  102.                     //Abandon Search
  103.  
  104.                     checked = true;
  105.                     break;
  106.                 }
  107.             }
  108.         }
  109.         if(checked == true)
  110.         {
  111.             printf("Case #%d: yes\n", rep);
  112.         }
  113.         else
  114.             printf("Case #%d: no\n", rep);
  115.     }
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement