Wybór najbardziej kalorycznego zestawu posiłków

Załóżmy, że jem pięć posiłków dziennie, a ponieważ jest siedem dni w tygodniu, mam przepisy na siedem każdego posiłku, łącznie na 35 przepisów. Każdy przepis ma liczbę kalorii. Każdy dzień musi zawierać jeden przepis na posiłek, a każdy przepis jest przypisany do konkretnego posiłku (np. Nie możesz zjeść naleśników na obiad). Wszystkie 35 przepisów musi znajdować się w roztworze, więc przepisu nie można powtórzyć w ciągu tygodnia.

Chcę znaleźć układ posiłków, który zapewni najbardziej równomierną liczbę kalorii dziennie - to znaczy chcę zminimalizować różnicę w całkowitej liczbie kalorii spożywanych z dnia na dzień.

To nie jest zadanie domowe - to prawda! Nie mogę wymyślić lepszego podejścia niż brutalna siła, a istnieje 7! ^ 4 kombinacji, co jest dużo.

Aby zastosować bardziej formalne podejście do problemu:

Masz 5 list po 7 liczb. Musisz zbudować 7 list po 5 liczb i znaleźć rozwiązanie, które ma minimalną różnicę między listą o największej sumie liczb a tą o najmniejszej.

Jeśli chcesz znaleźć optymalne rozwiązanie bez heurystyki, uważam, że nie masz innego wyboru niż wyliczyć, ale nie musisz wyliczyć ich wszystkich.

Niezależnie od tego, jakie rozwiązanie znajdziesz, kiedy zarejestrujesz je jako „najlepiej znalezione do tej pory”, zarejestruj jego wydajność w odniesieniu do swoich danych (uważam, że jest to różnica min-max). Następnie, jeśli gałąź rozwiązania jest wyraźnie poza drogą, przestań ją wyliczać. Protip: dni niezbudowane będą miały co najwyżej liczbę kalorii, która jest średnią wszystkich pozostałych posiłków. Wyobraź sobie, że masz listy [10, 2, 2, 1, 1, 0, 0]dla wszystkich 5 posiłków i zbudowałeś rozwiązanie 10 dla każdego posiłku na dzień 1. Wiesz, że pozostałe dni będą średnio 5 kalorii dziennie, więc różnica będzie wynosić co najmniej 45, a więc jeśli znalazłeś wcześniej rozwiązanie, powiedzmy, max - min = 10nie musisz iść dalej. Spróbujesz bezpośrednio innego menu dla pierwszego dnia.

To tylko hack, ale zbliży Cię
Tylko 3 posiłki
Zasadniczo klapki posiłki, jeśli zbliżą dwa dni do średniego C #

Lepszym rozwiązaniem byłoby zwrócenie boolen na Flopie i iterowanie aż do ukończenia.

Flop może stać się mądrzejszy. Możesz być w stanie nie flop śniadanie na flop lunch i kolację. Możliwe są permutacje kodu twardego. To bardziej przypomina sortowanie, w którym wartości flopa, a nie sortowanie.

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;
    }
}   

Najpierw oblicz średnią liczbę kalorii na posiłek. Następnie oblicz średnią liczbę kolorów na dzień. Będą to wskaźniki, które można zmierzyć. Następnie posortuj posiłki.

Teraz wybierz najwyższe i najniższe posiłki z tego rodzaju. Jeśli posiłek znajduje się w tym samym przedziale czasowym, będziesz musiał przejść do następnej najniższej lub najwyższej, aż znajdziesz posiłek, którego nie ma w tym przedziale czasowym (kolacja itp.). Zrób to dla pierwszych 4 posiłków (hi / low). Na 5. posiłek wybierz posiłek, który zbliży Cię do średniej. Zaoszczędź piąty posiłek do osobnego wiadra. Opłucz i powtórz 7 razy.

To będzie twój początkowy zestaw posiłków. To będzie ładne. Jeśli chcesz uzyskać optymalną dystrybucję, możesz dokonać dalszych udoskonaleń przy piątym posiłku.

Przejrzyj wiadro 5. posiłków i spróbuj zamienić posiłki na 5. posiłki między dniami, aby zobaczyć, czy posiłki jeszcze się wyrównają. Nadal będziesz musiał stosować te same zasady (nie więcej niż jeden posiłek na raz). Można, ale nie musi, otrzymać bardziej wyrównany zestaw. Użyj wcześniej obliczonych średnich, aby sprawdzić, czy nastąpiła poprawa, czy nie. Będzie dużo mniej kombinacji, ponieważ pierwsze 4 posiłki są ustalane w oparciu o wysokie / niskie.