This is a problem I created for myself, and I've been thinking about for a while and would like some other opinions on the matter. I'm using simple numbers just for example.(adsbygoogle = window.adsbygoogle || []).push({});

The problem:

Suppose you are hungry, and you need to eat at least 10 calories worth of food to get full, and you'd like to not go very much over that (you don't want a tummy-ache!). The foods available to you are Fish and Bread. A serving of fish has 2 calories, and a serving of bread has 4 calories. However, a serving of fish costs $1 and a serving of bread costs $5. What are the cheapest ways to get full?

The solutions:

Let f be the number of servings of fish and b be the number of servings of bread. Also, let c be total calories and p be the total price.

Now we have that:

[tex]2f + 4b \geq 10[/tex]

[tex]f + 5b = p[/tex]

At first this seems a lot like a linear programming problem, but if you actually work it out you'll soon see that you won't find the desired results (I won't fill up space with tableaus and pivots and whatnot). And that should be obvious, because one of the items will always have a lower price to calorie ratio: the optimum result will be all of just one item.

The problem is that the desired answer is one that doesn't gomuchover the target number of calories, and choosing all of one item will, in most cases, go over. BUT if the problem is changed to strictly equal to, there won't always be answer given certain parameters. And the entire time, we're trying to minimize cost, but also want to allow options (all of one item is boring!)

My solution, which illustrates the problem with treating it as an LP problem, is to "brute-force" the result.

[tex]

\begin{tabular}{ | c | c | c | c | }

\hline

t & b & c (2f+4b) & p (f+5b) \\

\hline

0 & 3 & 12 & 15 \\

1 & 2 & 10 & 11 \\

2 & 2 & 12 & 12 \\

3 & 1 & 10 & 8 \\

4 & 1 & 12 & 9 \\

5 & 0 & 10 & 5 \\

\hline

\end{tabular}

[/tex]

So in this case, solving the corresponding LP problem would've given 5 servings of fish and no bread, giving exactly 10 calories and only 5 dollars, the cheapest combination.

But we also see that you get exactly 10 calories with 1 fish and 2 bread, and 3 fish and 1 bread. And I would want these results as a hungry person, because even though I'm trying to be cheap, perhaps I wouldn't mind paying $3 more to get some variety in my diet.

Is there a better way to calculate these combinations than by brute-force? I feel like there should be but have so far come up dry. I would like a method that could accommodate an arbitrary number of food items.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Determining Cheapest Food Combinations (Seems like ILP problem, but also not)

**Physics Forums | Science Articles, Homework Help, Discussion**