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].
Expected Time Complexity: O(n * W)
Expected Auxiliary Space: O(W)