The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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!   
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.