我想知道是否有一些情况可以只使用其中之一来解决(即只能使用带重复的背包或不带重复的背包),或者这两种情况是否总是可以相互简化。没有重复的背包公式(就动态编程而言)是其中K(w,j)是指使用容量为k的背包和项目1...j可达到的最大值,而具有重复的背包的公式为其中K( w )是在背包容量w的情况下可达到的最大重量。
我正在尝试使用非整数值来减少背包DP算法所需的时间和空间。DP背包算法使用n x W矩阵,用结果填充它,但有些列永远不会填充-它们不匹配对象权重的任何组合。这样,它们只会在每一行上用零填充,只会浪费时间和空间。Substitution with hash:在Python中,字典插入的最坏情况为O(n),线性时间为O(1)“分期”。
我是不是遗漏了什么?背包DP算法的这种变体的复杂度是多少?