The Oregon Trail Knapsack Problem

In 1999, Jennifer Burd, John Ainsworth, Brian Casto and Sheau-Dong Lang published a paper entitled “Experiments with the ‘Oregon Trail Knapsack Problem’ ” Unfortunately, the pdf of the paper is low quality, so the paper is difficult to read, but it’s a fun election distraction.

There will be blood.


Abstract. This paper presents hybrid algorithms for a variation of the Bounded Knapsack Problem which we call the Oregon Trail Knapsack. Our problem entails imposing a cost as well as a weight limit, constraining the values of types of items by means of a variety of value functions, and allowing the value of one item type to be dependent on the presence or absence of another type in the knapsack. These modifications to the original problem make it more complex and require adaptations of known knapsack algorithms. To solve this problem, we combine constraint propagation techniques and domain pruning with classic branch and bound approaches that require a sorting of the items. Our experiments compare a constraint-language implementation with a simulation of the constraint-based system in a procedural language. Results indicate that the constraint-based solution is natural to the problem and efficient enough to solve large problem instances typical of the application.

Check out the iOS game or play online.

I vividly remember playing the game in grade school and recall that the game was stochastic, particularly if you needed to hunt. In addition, you had to make sequential decisions regarding hunting: do you extend your trip by a day so that you can eat? At some point, you had to hunt or you faced starvation. I was bad at hunting. I usually chose the robust strategy of playing a merchant so that I could purchase my food when I needed to. I did not starve, but I also did not achieve as many points as I could if I was not playing a wealthy character. From what I recall, no one escaped dysentery.

What was your Oregon Trail strategy?



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: