dynamic-programming - 有界背包问题的时间复杂度

Question

对于有重复问题的有界背包，我得到一个容量为 W 的背包。我必须装满背包，以使背包内物品的总价值最大化，其中每个物品都有相关的重量和价值 w 和 v。但是，我每个项目最多只能有 K 个。我找到了一种算法，我相信它的运行时间复杂度为 O(Wn)。但是，我发现很多消息来源说它可能是 O(WKn)。如果这是正确的时间复杂度，为什么会是 O(WKn)？

为了透明度，这确实是一个家庭作业问题。我只需要关于为什么时间复杂度为 O(WKn) 的帮助，除非我阅读的资料完全错误。

标签： dynamic-programmingknapsack-problem