Department of Computer Science & Engineering

A Knapsack problem is to select among n types of items of various values and weights to fill a knapsack of weight-carrying capacity b. The problem is NP-complete and has a dynamic programming algorithm of time complexity O(n b). If the given b is large, the optimum solution is periodic with its period equals to the weight of the best item. We introduce a new O(n 2 w 1 log (n w1)) algorithm that solves all instances b of the problem for a given set of items, where w1 is the weight of the best item and is usually much smaller than b. We conjecture that there are many other NP-complete number problems whose optimum solutions also become periodic for large instances and hence can be solved by similar algorithms.
Keywords: Knapsack, dynamic programming, shortest-path, NP, pseudo-polynomial

Pre-2018 CSE ID: CS2004-0775