Problem Submissions Solution
0-1 Knapsack Problem
Difficulty: Medium
Acceptance: %
Points: 30.00
Given n items where each item has some weight and profit associated with it and also given a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible.
Note: The constraint here is we can either put an item completely into the bag or cannot put it at all [It is not possible to put a part of an item into the bag].
Examples:
Expected Time Complexity: O(n * W)
Expected Auxiliary Space: O(W)
Constraints:
- 2 <= profit.size() = weight.size() <= 10^3
- 1 <= W <= 10^3
- 1 <= profit[i] <= 10^3
- 1 <= weight[i] <= 10^3
Companies:
Amazon Microsoft Visa Oracle Flipkart + 1 more
Topics:
Array Dynamic Programming
