0

So i just wanted to know the reason why is it happening. This gives TLE

public:
    int knapsack(vector<pair<int,int>> a , int wght , int i , vector<vector<int>> &dp){
        if(i==a.size() || wght == 0){
        return 0;
    }
    if(dp[i][wght] != -1) return dp[i][wght];
    else if(a[i].second > wght){
      return dp[i][wght] = knapsack(a , wght , i+1 ,dp);
    }
    else {
      int include = a[i].first + knapsack(a , wght - a[i].second , i+1 ,dp);
      int exclude = knapsack(a , wght , i+1 ,dp);
      dp[i][wght] = max(include , exclude);
      return dp[i][wght];
      }
    }
    public:
    int knapSack(int W, int wt[], int val[], int n) {
        vector<pair<int,int>> a;
        //memset(dp , -1 , sizeof(dp));
        
    vector<vector<int>> dp(1005, vector<int> (1005 , -1));
        for(int i=0;i<n;i++){
            a.push_back(make_pair(val[i],wt[i]));
        }
        return knapsack(a , W , 0 ,dp);
    }

while this one gets accepted

public:
    int dp[1005][1005];
    int knapsack(vector<pair<int,int>> a , int wght , int i){
        if(i==a.size() || wght == 0){
        return 0;
    }
    if(dp[i][wght] != -1) return dp[i][wght];
    else if(a[i].second > wght){
      return dp[i][wght] = knapsack(a , wght , i+1);
    }
    else {
      int include = a[i].first + knapsack(a , wght - a[i].second , i+1);
      int exclude = knapsack(a , wght , i+1);
      dp[i][wght] = max(include , exclude);
      return dp[i][wght];
    }
    }
    public:
    int knapSack(int W, int wt[], int val[], int n) {
        vector<pair<int,int>> a;
        memset(dp , -1 , sizeof(dp));
        for(int i=0;i<n;i++){
            a.push_back(make_pair(val[i],wt[i]));
        }
        return knapsack(a , W , 0);
    }

I know for a fact that the algo is correct since it is getting accepted , I also researched about vectors being slow but can't find the convincing answers. Please tell my why it is happening?

ShadowMitia
  • 2,411
  • 1
  • 19
  • 24
Abhijeet Srivastava
  • 43
  • 7
  • 1
    You are passing the vectors by value i.e. making a copy. That is O(n) operation, just pass them by reference. It is not a good idea to learn a language by doing these "puzzless", grab [a good c++ book](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Quimby Sep 18 '21 at 14:06
  • I am passing dp vector as a reference tho. – Abhijeet Srivastava Sep 18 '21 at 14:10
  • At the beginning of `int knapsack(vector...)` set a reference `int & dp_i_weight = dp[i][wght]` and use that one in the rest of the method instead of `dp[i][wght]`. Does it help? – ypnos Sep 18 '21 at 14:15
  • I was talking about `a`, but now I see that you copy it in both examples, so not sure. Vectors are definitely not slow, especially when you have correctly pre-allocated them. That said, `dp[1001][1001]` will be continuous, nested vectors are not, so it is less cache friendly. That might matter in this case. I usually just use one flattened `std::vector` for n-d arrays and do indexing manually or make a wrapper.. – Quimby Sep 18 '21 at 14:16
  • Try to passing `a` as `const vector&`, that should help a lot in both cases. – Quimby Sep 18 '21 at 14:20
  • Nothing worked Sadly @ypnos , I think the reasoning the other person gave about less cache friendly might be correct , I saw many other users code and none of them were using vectors for top down approach – Abhijeet Srivastava Sep 18 '21 at 14:31
  • 1
    Well that's good to know then. Btw. as in your problem the size is known at compile time you could also use `std::array`; however there is no 2d variant so `std::array>` would run into the same memory layout problem as std::vector. – ypnos Sep 18 '21 at 18:29

0 Answers0