Advertisement
193030

D. Bottle Time error

May 9th, 2020
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.79 KB | None | 0 0
  1. #include<fstream>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. //vector <int> vec{3,6,5,3,6};
  8. vector <int> vec;
  9.  
  10.  
  11. int result = 0;
  12. int counter = 0, tempCounter =0;
  13. int previousValue = 0;
  14. int KnapSack(int currentPos, int currentCapacity)
  15. {
  16.     int localCounter =0;
  17.   if(currentCapacity ==0)
  18.   {
  19.    // cout << "current cap return" << endl;
  20.       counter = tempCounter;
  21.      // localCounter = counter;
  22.      // cout << "Local counter: " << endl;
  23.       return counter;
  24.       exit(2);
  25.  
  26.   }
  27.   if(currentPos>=vec.size())
  28.   {
  29.       //cout << "current pos return" << endl;
  30.       return 0;
  31.   }
  32.   int currentValue = vec.at(currentPos);
  33.   if(currentValue<=currentCapacity)
  34.   {
  35.       currentCapacity = currentCapacity-currentValue;
  36.       currentPos++;
  37.       tempCounter++;
  38.       previousValue = currentValue;
  39.       KnapSack(currentPos,currentCapacity);
  40.   }
  41.   if(currentValue>currentCapacity)
  42.   {
  43.       currentCapacity = currentCapacity + previousValue;
  44.       --tempCounter;
  45.       KnapSack(currentPos,currentCapacity);
  46.   }
  47.  return 0;
  48. }
  49. void printVec()
  50. {
  51.     cout <<"VEc size: " << vec.size() << endl;
  52.     for(int i =0; i<vec.size();i++)
  53.     {
  54.         cout << vec.at(i) << " \t ";
  55.     }
  56.     cout << endl;
  57. }
  58. int main(){
  59.  
  60.     int W =0, n =0;
  61.     int x =0;
  62.     int broiTestove =0;
  63.     cin>>broiTestove;
  64.     while(broiTestove--)
  65.     {
  66.         cin>>W;
  67.         cin>>n;
  68.         for(int i =0; i< n; i++)
  69.         {
  70.             cin >> x;
  71.             vec.push_back(x);
  72.         }
  73.         sort(vec.begin(), vec.end());
  74.      //   printVec();
  75.         int ans = KnapSack(0, W);
  76.         cout << counter << endl;
  77.         vec.clear();
  78.         previousValue =0;
  79.         tempCounter =0;
  80.         counter =0;
  81.     }
  82.  
  83.     //cout << vec.size() << endl;
  84.  
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement