World's most popular travel blog for travel bloggers.

# Spandex knapsack?

, ,
Problem Detail:

I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple packages of each of these ingredients in various sizes.

I'll need at least 5kg of food to get me through the weekend, but I'm willing to carry up to 10kg of weight if it means I can achieve a more perfect balance of chocolate, marshmallow, and graham cracker. (My camping companions like s'mores, too.)

I really don't care about the weight, as long as it's in the range of 5-10kg. But the farther away from a 20/50/30 split, the sadder I'll be. :-(

I'm willing to devote some computational resources to this problem, but not too much; the weekend will be here before you know it. Can Computer Science help me?

#### Answered By : Nicholas Mancuso

This could be formulated as an ILP instance that searches for a feasible solution under your ratio constraints. However, you want to maintain the ratio as best as possible and not necessarily require it; therefore, we attempt to minimize the distance from this ratio by employing a Lagrangian relaxation of the constraints.

In this formulation $x_c$ is the 0-1 variable over each chocolate (similarly for marshmellow and graham cracker). $x_t$ is the integer variable that holds the number of selected items.

$$\min \lambda_c (\sum_c w_c x_c - .2 x_t) + \lambda_m (\sum_m w_m x_m - .5 x_t) + \lambda_g (\sum_g w_g x_g - .3 x_t)$$ $$s.t. \sum w_c x_c + \sum w_m x_m + \sum w_g x_g \leq x_t$$ $$\sum w_c x_c + \sum w_m x_m + \sum w_g x_g \leq 10$$ $$\sum w_c x_c + \sum w_m x_m + \sum w_g x_g \geq 5$$ $$x_c \in \{0,1\}, x_g \in \{0,1\}, x_m \in \{0,1\}$$ $$x_t \geq 0$$