One of the famous NP problems in combinatorics and decision theory is the “knapsack problem”, where the issue is to choose a subset that a) can fit in a total size constraint, and b) maximizes the total value, from a set of things of different values and sizes. This problem is presented somewhere in every CS department’s algorithms class and has lead to some important and interesting research.
I was wondering what this had to do with packing real knapsacks (well backpacks), and realized that there is another knapsack problem which is an engineering problem.
How do we choose and design the elements of the set so that a minimum functional specification is met, while being as far as possible below the size constraints?
This probably should be called the ‘ultra-light’ knapsack problem, because the real-world analog of this is how to select the lightest most functional equipment needed to
survive have a good time in wilds. It’s also a problem in software engineering, where the issue of weight becomes code size and maintainability as well as the performance of components of the program. These all are sort of related.
So how is this problem approached in practice?
Direct Minimization: The most obvious thing to do is to make everything light weight. As long as expected conditions permit, choose the 2lbs tarptent instead of the 6lbs winter supertent. This can be tricky – for example a ‘bivy sack’ and light tarp might weigh as much as a good single layer tent – so it’s important to be sure what and why you are using. What you choose must still do what you need it to do. If I design a software tool – I should choose the ‘best’ (by my performance criteria) algorithm but I need to be sure that the algorithm and its implementation actually to what they are supposed to do.
Journaling: One very effective technique in backpacking is to keep track of what equipment is used and what equipment isn’t. You don’t bring along things that you didn’t use on the next trip. There is an exception to this – you do bring first aid supplies, some repair tools and rain gear because you really might need it. On my trips, my cooking gear has (d)evolved to a folding plastic plate, a thermix cosy, a small light pot and plastic bags (see http://www.freezerbagcooking.com for my inspiration). I use Wendy’s chilli spoons because they are light and cheap. In software engineering, keeping a journal of command usage can help focus efforts on the parts of the program that actually get used. Journaling locations in the program gives a performance profile that can help identify bottlenecks. Not skimping on emergency equipment is the same as remembering to put in software diagnostics and interrupt handlers. Try()… Catch()… can be a real pain, but are important.
Multifunction: Why carry two single function tools if there is one tool that can do both things? There are good and bad aspects to this. Sometimes merging multiple functions is a great idea – a bandanna is one of the really useful things to take along – a light weight multitool or swissarmy knife is really good – and you can use a big tent stake to dig your catholes. The caution is that sometimes this doesn’t work. Sporks are my favorite trivial example – but seriously there is a sleeping bag that doubles as a parka. This sounds great until you realize that the time you need a dry sleeping bag is when you are nearly hypothermic and your parka is soaked. Designing an overly complex class that handles two distinctly different logical ideas is lame. Similarly, in the world of user interfaces, arbitrary placement of unrelated things on one ‘uber-checkbox’ is not a good way to engineer usability.
Validate: Always make sure the new light-weight equipment actually works. I do this in the real-world with two or three steps: first at home (for example trying a stove on my driveway), then on a “base camp” or car camping trip, and finally on a short real trip. In software engineering this the same as designing an acceptance suite and ensuring that new components actually pass it.
Distribute the Load: If you’re going in a group, you don’t all need to carry everything. Not everyone needs a stove. It’s all right to share a tent. Processes and threads can improve performance if you can implement them on appropriate hardware.