Wybór najbardziej kalorycznego zestawu posiłków

9

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.

dfaulken
źródło
3
Mam przeczucie, że jest to wariant problemu ze sprzętem do cięcia lub problemu z pakowaniem pojemników .
Doval
Dla wyjaśnienia - masz 7 przepisów na „pierwszy posiłek dnia”, 7 na „drugi posiłek”, 7 na „trzeci posiłek” i tak dalej? Czy przypisałbyś kiedyś przepis na „pierwszy posiłek” do „ostatniego posiłku dnia”? (Innymi słowy, czy
podałbyś
Poprawny; nie mógłbyś.
dfaulken
2
Czy wszystkie 35 przepisów ma znacząco różną liczbę kalorii? Jeśli zaokrąglisz liczbę kalorii do najbliższych 10 lub 50 kalorii, 7! ^ 4 może łatwo stać się 3! ^ 4 - co można łatwo obliczyć za pomocą brutalnej siły
Dan Pichelman
2
Koleś, jesz za dużo, jedzenie 5 posiłków dziennie spowoduje nadwagę.
Pieter B,

Odpowiedzi:

1

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.

Arthur Havlicek
źródło
To nie jest problem z koszem. Problem z koszem nie jest ustaloną liczbą pojemników i nie ustaloną liczbą elementów na pojemnik.
paparazzo
Tak masz rację. Źle to poprawię.
Arthur Havlicek
0

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;
    }
}   
paparazzo
źródło
1
czy jest jakiś sposób na dodanie do kodu wyjaśnienia lub komentarza, aby odpowiedź była bardziej pomocna / pouczająca? Myślę, że rozumiem, co się tam dzieje, ale nie jestem pewien.
Adam Wells,
@AdamWells Dodałem kilka komentarzy. Czego nie rozumiesz?
paparazzo
Po prostu nie kliknął flopem. Teraz ma sens, dzięki!
Adam Wells,
Nie wiem nawet, czy to jest kod Java. Czy to jest Niestety, moje dni Java i Cx są daleko za mną. Gdzie w ogóle jest główny?
Arthur Havlicek
@ArthurHavlicek Kod C #. Wyglądają podobnie.
paparazzo
0

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.

Jon Raynor
źródło