Associated Topics || Dr. Math Home || Search Dr. Math

### 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/
```
Associated Topics:
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search