Backpack with weight and item limit

Question

if I have a backpack with a weight limit of W, the item is Limit K and I have N elements, N> = k

I know how to maximize it, having a 3-dimensional memory array m [N] [W] [K] (N elements to consider, W weight on the left, K elements that can be selected) and, thus, do it in O ( N * W * K), but is there a way to do this even faster in a two-dimensional memory array and achieve faster complexity, something like O (N * W) complexity?

Answer 1

The memorandum that you use is incorrect: "m [N] [W] [K] (N items to consider, W weight on the left, K items on the left to choose from)." It does not capture complete information about which items are left to choose from and how many items are left to choose from.

The problem you are trying to solve is the Multidimensional Backpack , which is more complex than the classic problem.