The Knapsack problem mostly arises in resources allocation mechanisms. The name "Knapsack" was first introduced by Tobias Dantzig.
Auxiliary Space: O(nw) Time Complexity O(nw)
O(nw)