educative.io

Educative

https://www.educative.io/courses/grokking-dynamic-programming-patterns-for-coding-interviews/RM1BDv71V60

TIme Complexity: O(N^2)
Space Complexity: O(1)
Worked for both the given inputs

def solve_knapsack(profits, weights, capacity):
max_profit = 0
for i in range(len(weights)):
for j in range(len(weights)):
if not i == j and weights[i] + weights [j] <= capacity:
max_profit = max(max_profit,profits[i] + profits[j])
return max_profit

If there is a gap in my understanding please bridge it.

Complexity is less than the recursive. Why can’t I use iterative approach?

Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5633779737559040
Lesson: https://www.educative.io/collection/page/5668639101419520/5633779737559040/5666387129270272

Hey @learn!

The beauty of Computer Science is that there are always multiple solutions to a problem. You aren’t only limited to having one single solution. There is, therefore, no harm in using the iterative approach mentioned above. I think the particular lesson simply explored a few solutions and wanted to expand only on those.