9

Suppose I eat five meals a day, and since there are seven days in a week, I have recipes for seven of each meal, for 35 recipes in total. Each recipe has a calorie count. Each day must contain one recipe per meal, and each recipe is fixed to a particular meal (e.g. you can't have pancakes for dinner). All 35 recipes must be in the solution, so a recipe cannot be repeated during the week.

I want to find the arrangement of meals which will give the most even calorie count per day — that is, I want to minimize the difference in total calories consumed from day to day.

This isn't a homework problem — it's actually true! I can't come up with a better approach than brute-force, and there are 7!^4 combinations, which is a lot.

  • 3
    I have a gut feeling that this is a variation of the cutting stock problem or maybe the bin packing problem. – Doval Oct 18 '16 at 15:51
  • To clarify - you have 7 recipes for "first meal of the day", 7 for "2nd meal", 7 for "3rd meal", and so on? Would you ever assign a "first meal" recipe to a "last meal of the day"? (Put another way, would you serve pancakes for dinner?) – Dan Pichelman Oct 18 '16 at 15:58
  • Correct; you would not. – dfaulken Oct 18 '16 at 16:08
  • 2
    Do all 35 recipes have significantly different calorie counts? If you were to round the calorie counts to the nearest 10 or 50 calories, 7!^4 might easily become 3!^4 - which is easily computable via brute force – Dan Pichelman Oct 18 '16 at 18:55
  • 2
    Dude, you eat too much, eating 5 meals/day will get you overweight. – Pieter B Oct 18 '16 at 21:33
1

To make a more formal approach to your problem:

You have 5 lists of 7 numbers each. You need to build 7 lists of 5 number each, and find the solution which has the minimal difference between the list that has the biggest sum of numbers and the one with the smallest.

If you want to find the optimal solution with no heuristic, I believe you have little choice but to enumerate, but you don't have to enumerate all of them.

Whatever solution you find, when you register it as "best found so far", register its performance regarding your metric (I believe it's min-max difference). Then, if a solution branch is clearly off road from this, stop enumerating it. Protip: non-built days will have at best a calorie count that is the average of all remaining meals. So, imagine you have lists that are [10, 2, 2, 1, 1, 0, 0] for all 5 meals, and you built the solution 10 at each meal for day 1. You know the remaining days will be averaging 5 calories per day, so the difference will be at least 45 and so if you found previously a solution of, say, max - min = 10, you don't have to go any further. You will directly try another menu for day 1.

  • It is not a bin problem. A bin problem is not fixed number of bins and not fixed number of items per bin. – paparazzo Oct 18 '16 at 20:03
  • Yes you are right. Ill correct that. – Arthur Havlicek Oct 18 '16 at 20:14
0

This is just a hack but it will get you close
Only 3 meals
You basically flop meals if it makes the two days closer to the average C#

A better approach would be to return a boolen on Flop and iterate until complete.

Flop could get smarter. You may be in a position of not flop breakfast to flop lunch and dinner. There maybe hard code permutations. This is more like a sort where flop values rather than sort.

public static void MealEven()
{
    List<Day> Days = new List<Day>();
    Random rnd = new Random();
    decimal sum = 0;
    for(int i = 0; i<7; i ++)
    {
        int b = rnd.Next(100) + 40;
        int l = rnd.Next(100) + 60;
        int d = rnd.Next(100) + 80;
        Meal br = new Meal(enumMeal.b, b);
        Meal lu = new Meal(enumMeal.l, l);
        Meal di = new Meal(enumMeal.d, d);
        Day day = new Day(br, lu, di);
        Days.Add(day);
        sum += day.Calories;
    }
    decimal avg = sum / 7;
    foreach (Day d in Days.OrderBy(x => x.Calories))
        System.Diagnostics.Debug.WriteLine(d.Calories);
    System.Diagnostics.Debug.WriteLine("");

    Day low;
    Day high;
    Day lowLast = null;
    Day highLast = null;
    int count = 0;
    while (true)
    {   // first do high and low
        low = Days.OrderBy(x => x.Calories).FirstOrDefault();
        high = Days.OrderByDescending(x => x.Calories).FirstOrDefault();
        if (lowLast != null && lowLast == low && highLast == high)
            break;
        if (count > 1000)
            break;
        lowLast = low;
        highLast = high;
        count++;               
        Flop(ref high, ref low);
    }
    foreach (Day d in Days.OrderBy(x => x.Calories))
        System.Diagnostics.Debug.WriteLine("{0} {1} {2} {3}", d.Calories, d.B.Calories, d.L.Calories, d.D.Calories);
    System.Diagnostics.Debug.WriteLine("");

    // day a one on one pass
    for (int i = 0; i < 7; i ++)
    {
        for (int j = 0; j < 7; j++)
        {
            if (i == j)
                continue;
            Day d1 = Days[i];
            Day d2 = Days[j];
            Flop(ref d1, ref d2);
        }
    }

    foreach (Day d in Days.OrderBy(x => x.Calories))
        System.Diagnostics.Debug.WriteLine("{0} {1} {2} {3}", d.Calories, d.B.Calories, d.L.Calories, d.D.Calories);
    System.Diagnostics.Debug.WriteLine("");
}
public static void Flop (ref Day high, ref Day low)
{
    if(low.Calories > high.Calories)
    {
        int hold = low.B.Calories;
        low.B.Calories = high.B.Calories;
        high.B.Calories = hold;

        hold = low.L.Calories;
        low.L.Calories = high.L.Calories;
        high.L.Calories = hold;

        hold = low.D.Calories;
        low.D.Calories = high.D.Calories;
        high.D.Calories = hold;

    }
    decimal avg = (low.Calories + high.Calories) / (decimal)2;
    int bDiff = (high.B.Calories - low.B.Calories) < 0 ? 0 : (high.B.Calories - low.B.Calories);
    int lDiff = high.L.Calories - low.L.Calories < 0 ? 0 : (high.L.Calories - low.L.Calories);
    int dDiff = high.D.Calories - low.D.Calories < 0 ? 0 : (high.D.Calories - low.D.Calories);
    // only flop is one does not go past the average  
    if (bDiff > 0 && ((low.Calories + bDiff) < avg || (high.Calories - bDiff) > avg))
    {
        int hold = low.B.Calories;
        low.B.Calories = high.B.Calories;
        high.B.Calories = hold;
    }
    if (lDiff > 0 && ((low.Calories + lDiff) < avg || (high.Calories - lDiff) > avg))
    {
        int hold = low.L.Calories;
        low.L.Calories = high.L.Calories;
        high.L.Calories = hold;
    }
    if (dDiff > 0 && ((low.Calories + dDiff) < avg || (high.Calories - dDiff) > avg))
    {
        int hold = low.D.Calories;
        low.D.Calories = high.D.Calories;
        high.D.Calories = hold;
    }
}
public enum enumMeal {b, l, d};
public class Day
{
    public Meal B { get; set; }
    public Meal L { get; set; }
    public Meal D { get; set; }
    public Decimal Calories { get { return (Decimal)(B.Calories + L.Calories + D.Calories); } }
    public Day (Meal b, Meal l, Meal d )
    {
        B = b;
        L = l;
        D = d;
    }
}
public class Meal
{
    public enumMeal Type { get; set; }
    public int  Calories { get; set; }
    public Meal (enumMeal meal, int calories)
    {
        Type = meal;
        Calories = calories;
    }
}   
  • 1
    is there any way you could add an explanation or some comments to the code to get the answer to be more helpful/illuminating? I think i understand what's going on in there but i can't be sure. – Adam Wells Oct 18 '16 at 18:59
  • @AdamWells I added a couple comments. What do you not understand? – paparazzo Oct 18 '16 at 19:07
  • It just didn't click with flop. Makes sense now, thanks! – Adam Wells Oct 18 '16 at 19:26
  • I can't even tell if this is Java code. Is it ? Sorry, my Java and Cx days are far behind me. Where is the main anyway ? – Arthur Havlicek Oct 18 '16 at 19:39
  • @ArthurHavlicek The code C#. They look a lot the same. – paparazzo Oct 18 '16 at 19:54
0

First compute the average calorie count per meal. Then compute the average colorie count per day. These will be the metrics that one can measure against. Next sort the meals.

Now just pick the highest and lowest meals out of the sort. If a meal is in the same time slot you will have to go to the next lowest or highest until you find a meal that isn't in that time slot (dinner, etc.). Do this for the first 4 meals (hi/low). On the 5th meal, pick a meal that gets you closest to the average. Save off the 5th meal to a separate bucket. Rinse and repeat 7 times.

This will be your initial set of meals. This will be pretty even. If you want the optimal distribution some further refinement could be done with the 5th meal.

Go through the 5th meal bucket and try swapping meals 5th meals between days to see if the meals even out even further. You will still have to apply the same rules (not more than one meal per time). One may or may not get a more even set. Use the computed averages earlier to see if there is an improvement or not. There will be a lot less combinations since the first 4 meals are fixed based on high/low.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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