CODEWITHSUNDEEP
pythonalgorithmknapsack-problem
Giacomo d'Antonio
Giacomo d'Antonio

Reputation: 2275

0/1 Knapsack with few variables: which algorithm?

I have to implement the solution to a 0/1 Knapsack problem with constraints. My problem will have in most cases few variables (~ 10-20, at most 50).

I recall from university that there are a number of algorithms that in many cases perform better than brute force (I'm thinking, for example, to a branch and bound algorithm).

Since my problem is relative small, I'm wondering if there is an appreciable advantange in terms of efficiency when using a sophisticate solution as opposed to brute force.

If it helps, I'm programming in Python.

Upvotes: 4

Views: 1431

Answers (3)

rlinden
rlinden

Reputation: 2041

Brute force algorithms will always return the best solutions. The problem with them is that in exponential order problems they quickly become not feasible.

If you are guaranteed to have up to 20 variables, you will test no more than 1 million solutions (2^20= 1M). Hence, brute force is feasible and no other algorithm will return a better solution.

Heuristics are great, but they should be used only when we have no exact solution to the problem. There is a great book that might help you: How to Solve it, by Michalewicz.

Upvotes: 0

usamec
usamec

Reputation: 2384

You can either use pseudopolynomial algorithm, which uses dynamic programming, if the sum of weights is small enough. You just calculate, whether you can get weight X with first Y items for each X and Y. This runs in time O(NS), where N is number of items and S is sum of weights.

Another possibility is to use meet-in-the middle approach. Partition items into two halves and: For the first half take every possible combination of items (there are 2^(N/2) possible combinations in each half) and store its weight in some set. For the second half take every possible combination of items and check whether there is a combination in first half with suitable weight. This should run in O(2^(N/2)) time.

Upvotes: 1

Qnan
Qnan

Reputation: 3744

Brute force stuff would work fine for 10 variables, but for, say, 40 you'd get some 1000'000'000'000 possible solutions, which would probably take too long to enumerate. I'd consider approximate algorithms, e.g. the polynomial time algorithm (see, e.g. http://math.mit.edu/~goemans/18434S06/knapsack-katherine.pdf) or use a search algorithm such as branch-and-bound, maybe with an additional heuristic.

Upvotes: 0

Related Questions