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].
Example 1
Input: W = 5, profit[] = [10, 40, 30, 50], weight[] = [5, 4, 6, 3]
Output: 50
Explanation: Choose the last item (profit 50, weight 3) for a total value of 50.
Example 2
Input: W = 4, profit[] = [1, 2, 3], weight[] = [4, 5, 1]
Output: 3
Explanation: Choose the last item, which weighs 1 unit and has a profit of 3.
Sign in to write, run, and submit your solution against the full test suite.