Algorithms for the Knapsack Problem
Date: 04/08/98 at 12:18:20 From: Felix Okoh Subject: algorithm I am finding difficulty solving this problem. Can you help me? I am supposed to find an algorithm for this problem. The Knapsack Problem One day, our friend Bob is taken to a room full of toys and told that he can keep as many toys as he can fit in his knapsack (backpack). Clearly, he has to be careful - he wants to be sure to get as many of the most fun toys as possible, without wasting space in his knapsack on the less fun toys. Being the clever guy that he is, he decides to assign a value (in terms of Fun-ness) to each toy. Then he figures out how much space each toy will take up in his knapsack. His knapsack is very flexible, so he doesn't have to worry about the shapes of the toys, only the sizes. Find an algorithm for the problem.
Date: 04/09/98 at 12:20:48 From: Doctor Celko Subject: Re: algorithm If you find a general answer, please publish it! This is what is called an NP complete problem, which means that as the number of items in the knapsack increases, the time and resources needed to solve it increase at a fantastic rate and cannot be done with all the computers in the world. What you have to do is try all possible combinations of toys and score them on the "fun scale." Another algorithm is the greedy algorithm, where you start with the highest valued toy and put it in, then repeat the process until the knapsack is full. This will not work in all cases, but at least you will get an answer. A better algorithm is called "backtracking." You try putting toys in the knapsack and when it overflows, you see if you can replace a toy with a smaller toy in the leftover pile that has the same or more "fun points." This doesn't always work either, but it usually gets better results than the Greedy algorithm. -Doctor Celko, The Math Forum Check out our web site! http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.