# Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples allowed) with the lowest total price.

Does anyone have any advice as to how to approach this problem? Is there a certain algorithm that exists that takes in a list of possible items, and finds a permutation that minimizes one property of the item(s), in this case the price, and also makes sure that the sum of each property meets a certain range, in this case nutritional properties like carbs and protein? Any advice is greatly appreciated. Thanks!

Use integer linear programming. Suppose you have $$n$$ foods. Let $$x_1,\dots,x_n$$ be zero-or-one variables, with the intention that $$x_i=1$$ means you include food $$i$$ in the combination. Then the price is a linear function of these $$x$$'s, so that's your objective function you are minimizing. If you want the total carbs to be within a range, you can express that as a linear inequality (e.g., $$\ell \le c_1 x_1 + \dots + c_n x_n \le u$$, where $$\ell,u$$ are the lower and upper bounds of the range and $$c_i$$ is the amount of carbs in food $$i$$). Feed this to an off-the-shelf ILP solver, and it should give you the optimal answer.

Since you are asking in Computer Science, I very much recommend George Dantzig's "Linear Programming and Extensions". It explains linear programming in a way that a normal human being (like me) can understand. The link has links to three .pdf files of this book.

https://www.rand.org/pubs/reports/R366.html

At the outset, I'll write this up in Java, or at least show my line of thinking from a Java standpoint.

Given that we're looking at Food items, we'll define a Food class that has:

A field/attribute for type of food (In our case, we'll take "raw" and "un-raw"). A field/attribute for the name of the food. A field/attribute for the price of the food.

Note that I am not taking into consideration the actual caloric properties or anything health-associated for now. If I can come back to this answer later, I'll see if I have anything to offer on that front.

We'll define this class and then for our algorithm we'll take in as input a List, or informally speaking, a list of Objects that are all of type Food. We'll denote this as List A.

To solve the problem of minimizing price, we could use some sorting algorithm (quicksort, right?) on the item prices, and once we've sorted in ascending order, iterate through this list and add to a new List, denoted as List B, only those items which have the type "raw."

Your final List B would have only raw foods and those raw foods in ascending order of price.

Now let's take a look at this caloric/health-property part of the problem. We'll say that you have three inputs for the algorithm:

1. A List of Food items
2. A price bound, expressed as a double/decimal number
3. A calorie bound, expressed as a whole number

We'll see that what you're doing is minimizing on two fronts instead of one. The first front we minimize on is price. What we'll do is we'll iterate through List A and add to List B only those items that are raw.

## SORTING ON PRICE, LIST B

We'll then sort through List B using price, so that we have raw foods arranged in ascending order of price. We'll take the sum of all the items' prices and see where we're at. Denote this as initialTotal.

If we're within the price bound, then we're good, and if we aren't... then there's problems. We may have to take out certain items based on price, but the interesting thing is that we'll have to also consider caloric intake there...

Let's assume you're within the price bound, so initialTotal <= priceBound.

## SORTING ON CALORIES, LIST B

We'll add up all the calories of all the items in List B, and denote this as initialCal.

If we're within the caloric bound, denoted as calBound, then initialCal <= calBound. If both conditions relating to total price and total cal hold, then we can return List B as it is.

Let us suggest the calories are off. What we can do is we can sort on the calories, and reorder List B. We could potentially reverse-sort on List B so we see the most caloric-heavy foods first, and the least caloric-heavy foods last.

We may be able to isolate some subset of List B as having the most caloric-heavy foods, say the k element subset of foods within List B.

We need to find the combination then of foods to get rid of such that initialCal <= calBound. Whatever remains, we can return.

I know this is a rather long answer, but hopefully in a few days I may be able to come and answer some more/significantly reformat the answer to be more helpful. My apologies for this being incomplete, as it were. I'll try to fix this soon.

Good luck with the diet!

• Sorry for the late reply! But thanks for the answer. I'm not particularly trying to stay within just a caloric limit, but really, I'm trying to make sure that I get enough macro and micro nutrients each day for the cheapest price possible. My idea is to maybe first evaluate each food with a calorie - nutrient density ratio, sort that, and go from there. That way id minimize the empty calories. I was hoping that there would be some sort of exact formula to use for this, but I guess I'll just have to use multiple iterations to keep optimizing the result. Anyways, thanks for your answer! – Shashank Rajesh Dec 6 '18 at 12:10