0-1 knapsack problem complexity is NP-complete.Which algorithm can solve it in polynomial time and under which conditions?
Well, of course you can solve it heuristically in polynomial time. I remember a classic greedy heuristic based on taking first the elements that maximize c_i/w_i, where c_i and w_i are the value and weight of the i-th object, respectively.
I also believe it can be solved approximately through dynamic programming, as you should be able to find with a little research.
As for special polynomial cases that can be solved to optimality, I'll leave the answer to someone which has more experience on the topic.
Dynamic programming solves it in O(Kn) time, where K is the knapsack size. If K is polynomial in n, this time is polynomial.
Dear Yefim,
Dynamic programming solves in pseudo polynomial times. Can you tell me the algorithm which can be solve it in polynomial times.
The problem is well-known to be NP-hard, thus you may hope a polynomial time exact algorithm only for special cases, that is with a special structure on the weights wi and the utilities ui of the objets. In particular the 0-1 Knapsack (and also is bounded version) is polynomially solvable :
- For divisible items weights, that is w(i+1) is a multiple of w(i) for some indexation.
- For cross ratio ordered instances
For definitions and references, see the article of Deineko &Woeginger in Operations Research Letters 39 (2011) 118–120, " A well-solvable special case of the bounded knapsack problem"
Lattice reduction methods (which are polynomial time) can be used for certain knapsack problems. A web search should locate a number of good references.
Some knapsacks are equivalent to partitioning problems. Binary partitioning can sometime be solved with mincut-maxflow methods or transport methodologies, which are polynomial (with state of the art algorithms). Look up transport problems in optimization, also the following papers and their citations is a good starting point.
@article{horowitz1974computing,
title={Computing partitions with applications to the knapsack problem},
author={Horowitz, Ellis and Sahni, Sartaj},
journal={Journal of the ACM (JACM)},
volume={21},
number={2},
pages={277--292},
year={1974},
publisher={ACM}
}
@article{magazine1981fully,
title={A fully polynomial approximation algorithm for the 0--1 knapsack problem},
author={Magazine, MJ and Oguz, Osman},
journal={European Journal of Operational Research},
volume={8},
number={3},
pages={270--273},
year={1981},
publisher={Elsevier}
}
- Badges
- Science topic
- Similar topics
- Comment