python - 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)，它是两个循环的总和(忽略常量)。然后我在网上读到这种方法具有指数时间复杂度(不是来自一个来源，许多博客也说指数时间复杂度)。我看不出它是如何发生的，例如考虑以下任何示例:

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) 对象，以及大约 sqrt(N) 位长的总容量。

这使得total_capacity约为sqrt(2)^N，并且您的解决方案需要O(sqrt(N)*sqrt(2)^N)时间，这当然是指数级的.