时间戳

首页 > 解决方案 > 0-1 背包如何具有数学上的指数时间复杂度？

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

问题描述

我写了一个算法来解决 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 并不会导致任何指数增长。那么他们怎么能说这个算法在数学上是指数的。

标签： pythonalgorithmperformancetime-complexityknapsack-problem

解决方案

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

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

推荐阅读