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!

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.

END OF INITIAL ANSWER

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 at 12:10

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.