algorithm - 有重量和元素限制的背包

Question

如果我有一个背包，重量限制为 W，元素限制为 K，我有 N 件元素，N >= k

我知道如何通过拥有一个 3 维内存数组 m[N][W][K](要考虑 N 个项目，剩下 W 个权重，剩下 K 个项目可供选择)来最大化它，因此在 O (N * W * K) 复杂度，但有没有办法在二维内存数组中更快地完成它并实现更快的复杂度，比如 O(N * W) 复杂度？

Answer 1

您使用的内存不正确:“m[N][W][K](要考虑的 N 个项目，剩余 W 个权重，剩余 K 个项目可供选择)”。它不会捕获关于哪些项目可供选择以及有多少项目可供选择的完整信息。

您要解决的问题是 Multi dimensional knapsack ，这比经典问题更复杂。