educative.io

Educative

Knapsack Solution As Per Course Pattern - Memo

int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity, unordered_map<string, int>& memo, int currentIndex) {

    string key = to_string(capacity) + "#" + to_string(currentIndex);

    if(memo.find(key) != memo.end()) return memo[key];

    if(capacity <= 0 || currentIndex >= profits.size() || profits.size() != weights.size()) {

      return 0;

    }

    //branching factor 2;

    int profit1 = 0;

    if(capacity - weights[currentIndex] >= 0) {

      profit1 = profits[currentIndex] +  solveKnapsack(profits, weights, capacity - weights[currentIndex], memo, currentIndex+1);

    }

    int profit2 = 0;

    profit2 = solveKnapsack(profits, weights, capacity, memo, currentIndex+1);

    memo[key] = max(profit1, profit2);

    return memo[key];

  }

//T: O(n*c); S = o(n + n*c)

  int solveKnapsack(const vector<int> &profits, const vector<int> &weights, int capacity) {

    unordered_map<string, int> memo;

    return solveKnapsack(profits, weights, capacity, memo, 0);

  }

Hi @Rupinder_Ghotra

We appreciate your efforts. Your code is working perfectly fine :slight_smile:

Happy learning,

1 Like