0-1 背包如何具有数学指数时间复杂度？

Question

我写了一个算法来解决 0-1 背包问题，效果非常好，如下所示：

def zero_one_knapsack_problem(weight: list, items: list, values: list, total_capacity: int) -> list:
    """
    A function that implement dynamic programming to solve the zero one knapsack problem. It has exponential
     time complexity as supposed.

    :param weight: the weight list each element correspond to item at same index
    :param items: the array of items ordered same as weight list and values list
    :param values: the values list
    :param total_capacity: the total capcaity of knapsack
    :return: How to fill the knapsack
    """

    items_length = len(items)+1
    total_capacity += 1
    # Create The table
    table = [[0 for w in range(total_capacity)] for y in range(items_length)]

    for i in range(1, items_length):
        for j in range(total_capacity):
            if weight[i-1] > j:   # Item does not fit
                pass
            else:
                # calculate Take It or Not
                table[i][j] = max(values[i-1]+table[i-1][j-weight[i-1]], table[i-2][j])
    print("The optimal value to carry is: ${}".format(table[items_length-1][total_capacity-1]))

根据分析，时间复杂度为 seta(items_length * total_capacity)，这是 2 个循环的总和（忽略常量）。然后我在网上读到这种方法具有指数时间复杂度（不是来自一个来源，许多博客也说指数）。我看不出它是怎么来的，例如考虑以下任何一个例子：

1-) 10 * 100000000000 = 1×10¹²
2-) 11 * 100000000000 = 1.1×10¹²
3-) 12 * 100000000000 = 1.2×10¹²

# difference between each
2 and 3 = 100000000000 = 1.2*10^12 - 1.1*10^12
1 and 2 = 100000000000 = 1.1*10^12 - 1*10^12

如您所见，将输入增加 1 并没有导致任何指数增长。那么他们怎么能说这个算法在数学上是指数的。

Answer 1

对于 N 位大小的问题，例如，您可以拥有权重约为 sqrt(N) 位长的 sqrt(N) 对象，并且 total_capacity 约为 sqrt(N) 位长。

这使得 total_capacity 关于 sqrt(2)^N，而您的解决方案需要 O(sqrt(N)*sqrt(2)^N)时间，肯定是指数级的。

0-1 背包如何具有数学指数时间复杂度？

How does 0-1 knapsack have mathmatically exponential time complexty?

python

algorithm

performance

knapsack-problem

time-complexity