Knapsack Problem
Series: bsc
Have you ever tried to perfectly pack a suitcase to avoid going over the weight limit? That’s similar to the challenge I faced for my university project – fitting scientific experiments into a high-altitude balloon without exceeding its capacity.
Instead of clothes and souvenirs though, I had to pack equipment like spectrometers, imagers, and detectors. The goal was to launch atmospheric research experiments 20+ miles into the sky without the balloon breaking apart!
To tackle this, I used something called a 0-1 knapsack problem model. In short, it’s an optimization method for maximally filling a “knapsack” (the balloon) without going over a weight limit. Each item (experiment) has both a weight and a value. The objective is to maximize the total value you can fit based on the weight restriction.
I considered 11 potential high-tech experiments that each provide unique atmospheric readings. However, the balloon could only handle 14 kg given its electric and structural constraints. Using the knapsack model, I systematically computed the best combination of experiments that maximizes scientific value without weighing down the balloon.
In the end, the optimized solution carries 6 experiments projected to bring in £370k in research grants for future projects. I also modeled larger balloon capacities and experiment costs to find even better options if budget allows.
While it was framed around balloons and sensors, this project demonstrated a versatile optimization technique. All sorts of real-world packing, scheduling, and planning problems can be solved using this type of 0-1 knapsack mathematical model. Whether it’s making business investment decisions, budgeting projects, or traveling light – the knapsack approach helps you maximize decisions in a constrained setting!
To see more details, check out the paper
Disclaimer: This project was completed as part of my BSc in Mathematics at Manchester Metropolitan University. The project was supervised by Dr. Keith Yates and Dr. Philip Sinclair. This blog post is an LLM generated text, based upon the hand-written report.