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);
}