iGEM Davidson – Missouri Western 2010: Human Practices

The Knapsack Game

"How can you possibly solve a math problem with bacteria?"

This is a question that we are frequently asked while discussing our research with other students, faculty, and community members because our goal was to solve the knapsack problem. The knapsack problem is an NP-complete mathematical problem that grows complex rapidly. For this reason, we would use a bacterial computer to solve this problem. First, we needed a simple way to demonstrate what the knapsack problem is and how it grows more complex.

For our human practice we chose to design a game to simulate the knapsack problem that can be used as an educational resource. From middle schools to undergraduate courses that discuss NP-complete problems, this game has the potential to have a broad impact on educating the public. The Knapsack Game makes it easy to understand the complexity of NP-complete problems and allows for a fun and innovative learning experience!

The Knapsack Game has two modes: tutorial and challenge. Each mode asks the player to fill a knapsack of a certain capacity with given weighted items. The tutorial gives tips about the type of problem and only uses six weighted items. The challenge offers no help and asks the player to choose from nine weighted items. It becomes obvious that the more objects available to choose from, the more combinations are possible to fill the knapsack, thus showing the player the complexity of the problem.

Using this game as a teaching tool has proven useful in helping to explain a complex mathematical problem to others and it will continue to do so in the future.

Click HERE to play the Knapsack Game.