CODEWITHSUNDEEP
pythonalgorithmperformancetime-complexityknapsack-problem
KMG
KMG

Reputation: 1501

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

I wrote an algorithm to solve 0-1 knapsack problem which works perfect which is as follows:

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]))

From the analysis the time complexity is seta(items_length * total_capacity) which is the summation of the 2 loops together(ignoring constants). Then i read online that this method has exponential time complexity(Not from one source many blogs says exponential also). Which I can't see how it comes for example consider any of below examples:

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

as you can see increasing input by 1 didn't cause any exponential growth. So how can they say this algorithm is exponential in a mathematical way.

Upvotes: 2

Views: 437

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59204

With a problem size of N bits, you can have, for example, sqrt(N) objects with weights about sqrt(N) bits long, and total_capacity about sqrt(N) bits long.

That makes total_capacity about sqrt(2)N, and your solution takes O(sqrt(N)*sqrt(2)N) time, which is certainly exponential.

Upvotes: 2

Related Questions