背包问题的最佳和最差情况

Question

我想知道背包问题的最佳和最差情况。我猜最好的情况应该是所有对象的值和权重具有相同的值。例如：

int[] values = new int[] { 5, 5, 5};
int[] weights = new int[] { 9, 9, 9}; 

但是我对最坏的情况一无所知。

非常感谢！

Answer 1

由于相对于算法或问题的解决方案定义了最佳和最坏的情况，所以我认为您是指背包问题的著名动态编程解决方案。

背包算法的动态编程解决方案是在pseudo-polynomial algorithm时间运行的O(nW)，其中n表示商品数量，W表示最大重量。因此，只需将最大权重设置为任意高的值，就可以使该算法的运行效果非常差。特别是，将每个权重设置为2^n将使该算法在O(2^n)时间运行。