Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<fstream>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- using namespace std;
- //vector <int> vec{3,6,5,3,6};
- vector <int> vec;
- int result = 0;
- int counter = 0, tempCounter =0;
- int previousValue = 0;
- int KnapSack(int currentPos, int currentCapacity)
- {
- int localCounter =0;
- if(currentCapacity ==0)
- {
- // cout << "current cap return" << endl;
- counter = tempCounter;
- // localCounter = counter;
- // cout << "Local counter: " << endl;
- return counter;
- exit(2);
- }
- if(currentPos>=vec.size())
- {
- //cout << "current pos return" << endl;
- return 0;
- }
- int currentValue = vec.at(currentPos);
- if(currentValue<=currentCapacity)
- {
- currentCapacity = currentCapacity-currentValue;
- currentPos++;
- tempCounter++;
- previousValue = currentValue;
- KnapSack(currentPos,currentCapacity);
- }
- if(currentValue>currentCapacity)
- {
- currentCapacity = currentCapacity + previousValue;
- --tempCounter;
- KnapSack(currentPos,currentCapacity);
- }
- return 0;
- }
- void printVec()
- {
- cout <<"VEc size: " << vec.size() << endl;
- for(int i =0; i<vec.size();i++)
- {
- cout << vec.at(i) << " \t ";
- }
- cout << endl;
- }
- int main(){
- int W =0, n =0;
- int x =0;
- int broiTestove =0;
- cin>>broiTestove;
- while(broiTestove--)
- {
- cin>>W;
- cin>>n;
- for(int i =0; i< n; i++)
- {
- cin >> x;
- vec.push_back(x);
- }
- sort(vec.begin(), vec.end());
- // printVec();
- int ans = KnapSack(0, W);
- cout << counter << endl;
- vec.clear();
- previousValue =0;
- tempCounter =0;
- counter =0;
- }
- //cout << vec.size() << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement