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].

Topics

Companies

Articles

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
Locked Content
Access Restricted: Please Login to access the code editor and test cases.