Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <list>
- #include <vector>
- using namespace std;
- vector <vector<int> > nList;
- int i = 0, x = 0;
- void subset_sum_recursive(list<int> numbers, int target, list<int> partial)
- {
- int s = 0;
- for (list<int>::const_iterator cit = partial.begin(); cit != partial.end(); cit++)
- {
- s += *cit;
- }
- if(s == target)
- {
- for (list<int>::iterator cit = partial.begin(); cit != partial.end(); cit++)
- {
- int val = int(*cit);
- nList[i].push_back(val);
- }
- i++;
- }
- if(s >= target)
- return;
- int n;
- for (list<int>::const_iterator ai = numbers.begin(); ai != numbers.end(); ai++)
- {
- n = *ai;
- list<int> remaining;
- for(list<int>::const_iterator aj = ai; aj != numbers.end(); aj++)
- {
- if(aj == ai)continue;
- remaining.push_back(*aj);
- }
- list<int> partial_rec=partial;
- partial_rec.push_back(n);
- subset_sum_recursive(remaining,target,partial_rec);
- }
- }
- void subset_sum(list<int> numbers,int target)
- {
- subset_sum_recursive(numbers,target,list<int>());
- }
- /* int main()
- {
- std::list<int> a;
- a.push_back (3); a.push_back (9); a.push_back (8);
- a.push_back (4);
- a.push_back (5);
- a.push_back (7);
- a.push_back (10);
- int n = 15;
- subset_sum(a, n);
- for(int i = 0, l = 15; i < l;i++)
- {
- for(int x = 0, y = int(nlist[i].size());x < y;x++)
- {
- printf("%d ", nlist[i][x]);
- }
- printf("\n");
- }
- return 0;
- } */
- int main(void)
- {
- int t, n, x, y, z;
- scanf("%d", &t);
- for(int rep = 1;rep <= t;rep++)
- {
- int GP, GC, GF;
- scanf("%d%d%d", &GP, &GC, &GF);
- scanf("%d", &n);
- vector<int> nP, nC, nF;
- for(int i = 0;i < n;i++)
- {
- scanf("%d%d%d", &x, &y, &z);
- nP.push_back(x);
- nC.push_back(y);
- nF.push_back(z);
- }
- list<int> newn(nP.begin(), nP.end());
- nList.clear();
- nList.resize(n);
- subset_sum(newn, GP);
- int sumC = 0, sumF = 0;
- bool checked = false;
- for(int i = 0, l = int(nList.size());i < l;i++)
- {
- if(int(nList[i].size()) != 0)
- {
- for(int j = 0, a = int(nList[i].size());j < a;j++)
- {
- sumC += nC[int(find(nP.begin(), nP.end(), nList[i][j]) - nP.begin())];
- sumF += nF[int(find(nP.begin(), nP.end(), nList[i][j]) - nP.begin())];
- }
- if(sumC == GC && sumF == GF)
- {
- //Abandon Search
- checked = true;
- break;
- }
- }
- }
- if(checked == true)
- {
- printf("Case #%d: yes\n", rep);
- }
- else
- printf("Case #%d: no\n", rep);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement