Zero one knapsack

Question

Zero one knapsack You are given two arrays weights and profits of size N where weights[i] denotes the weight of the ith item and profits[i] denotes the profit you will earn if you steal the ith item. You are also given a positive integer capacity that denotes the total weight your knapsack can hold. Write a function to find and return the maximum profit you can earn by stealing from these N items such that they fit in your knapsack. Example 1 > - **Input:** weights = [6, 4, 5, 3], profits = [7, 3, 2, 6], capacity = 10 > - **Output:** 13 > - **Explanation:** We can only pick the first and the last item as they give us the maximum profit. Example 2 > - **Input:** weights = [4, 5, 1], profits = [1, 2, 3], capacity = 4 > - **Output:** 3 > - **Explanation:** We can only pick the last item as this is the only one that will fit in our knapsack. Example 3 > - **Input:** weights = [4, 5, 6], profits = [1, 2, 3], capacity = 3 > - **Output:** 0 > - **Explanation:** We cannot fit any item into the knapsack.

Accepted Answer

Optimal Solution: Time Complexity O(N*capacity), Space Complexity O(1). Codeintuition provides an interactive coding environment for this problem.