时间戳

首页 > 解决方案 > 如何划分三个类别的组合？

php - 如何划分三个类别的组合？

问题描述

我有一个包含 3 类食谱的数组，早餐、午餐和晚餐。这些类别中的每一个都有 10 个独特的食谱。

$recipes = [
    'breakfast' => [
        0 => [
            'title' => 'eggless waffles',
            'calorie' => 210,
        ],
        1 => [
            'title' => 'blueberry oatmeal',
            'calorie' => 161,
        ],
        ...
     ],
    'lunch' => [9],
    'dinner' => [9]
];

我想为每天排序并创建 3 个食谱的组合

$days = array_fill(0, 6, [1 => [], 2 => [], 3 => []]);

每个食谱都有一个卡路里量，并且每个最后一天都应该有一个组合（包括 1 份早餐、1 份午餐和 1 份晚餐）与按最接近 500 的 3 份食谱组合订购的食谱

例如，如果第 1 天的组合食谱（早餐、午餐和晚餐）卡路里总计 660，而第 2 天为 400。可能将早餐从第 2 天切换到第 1 天可能会使两者都达到最接近 500，但也有可能将第 3 天的早餐切换到第 1 天，将第 2 天的早餐切换到第 3 天，这可能会使所有 3 人的命中率也接近 500。

所以第 1、2、3、4、5、6 和 7 天应该有 3 个食谱（早餐、午餐和晚餐）

$final = [
    0 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
     1 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
    2 => [
        'breakfast' => [...],
        'lunch' => [...],
        'dinner' => [...],
    ],
    ...
];

自从我陷入僵局已经有好几天了，我不知道如何将这些数组排序为每天 3 个的组合。（我知道我没有提供很多代码）

编辑1：这是我到目前为止所得到的：

class Combinations {

    private $days;

    public function __construct(){
        $this->days = array_fill(1, 7, [1 => [], 2 => [], 3 => []]);
    }

    public function create(){
        $median = 600;

        foreach($this->days as $day => $categories){
            while($this->dayIsIncomplete($day)){
                $recipes = [];
                foreach($categories as $category => $value){
                    $recipes[$category] = $this->getRandomRecipe($category);
                }

                // add random meals to first day
                if($day === 1){
                    $this->days[$day] = $recipes;
                    continue;
                }

                foreach($recipes as $category => $recipe){
                    foreach($this->days as $dayKey => $mealsArray){
                        $originalMacros = $this->totalMacros($mealsArray);

                        // remove $recipe category from mealsArray, and merge it ($recipe)
                        $filteredMacros = $this->totalMacros(array_merge([$recipe], array_filter($mealsArray, function($key) use($category){
                            return $key !== $category;
                        }, ARRAY_FILTER_USE_KEY)));

                        // if original is not closer to median
                        if(($originalMacros - $median) * ($originalMacros - $median) < ($filteredMacros - $median) * ($filteredMacros - $median)){
                            // flip current recipes
                            // switch D2B ($recipe) with D1B
                        }
                    }
                }
            }
        }
    }

    public function getRandomRecipe(int $category){
        $recipes = []

        if($category === 1){
            $recipes[] = ['id' => 1, 'calorie' => 310];
            $recipes[] = ['id' => 2, 'calorie' => 360];
            $recipes[] = ['id' => 3, 'calorie' => 450];
            $recipes[] = ['id' => 4, 'calorie' => 330];
            $recipes[] = ['id' => 5, 'calorie' => 220];
            $recipes[] = ['id' => 6, 'calorie' => 390];
            $recipes[] = ['id' => 7, 'calorie' => 400];
            $recipes[] = ['id' => 8, 'calorie' => 320];
            $recipes[] = ['id' => 9, 'calorie' => 460];
        }

        if($category === 2){
            $recipes[] = ['id' => 10, 'calorie' => 420];
            $recipes[] = ['id' => 11, 'calorie' => 360];
            $recipes[] = ['id' => 12, 'calorie' => 450];
            $recipes[] = ['id' => 13, 'calorie' => 310];
            $recipes[] = ['id' => 14, 'calorie' => 320];
            $recipes[] = ['id' => 15, 'calorie' => 490];
            $recipes[] = ['id' => 16, 'calorie' => 440];
            $recipes[] = ['id' => 17, 'calorie' => 520];
            $recipes[] = ['id' => 18, 'calorie' => 560];
        }

        if($category === 3){
            $recipes[] = ['id' => 19, 'calorie' => 510];
            $recipes[] = ['id' => 20, 'calorie' => 660];
            $recipes[] = ['id' => 21, 'calorie' => 750];
            $recipes[] = ['id' => 22, 'calorie' => 610];
            $recipes[] = ['id' => 23, 'calorie' => 580];
            $recipes[] = ['id' => 24, 'calorie' => 690];
            $recipes[] = ['id' => 25, 'calorie' => 710];
            $recipes[] = ['id' => 26, 'calorie' => 620];
            $recipes[] = ['id' => 27, 'calorie' => 730];
        }

        return $recipes[array_rand($recipes)];
    }

    public function dayIsIncomplete($day){
       return !empty($this->days[$day][1]) && !empty($this->days[$day][2]) && !empty($this->days[$day][3]);
    }

    public function totalMacros($array){
        $total = 0;
        foreach ($array as $key => $value) {
            $total += $value['calorie'];
        }
        return $total / 2;
    }
}

编辑2：

我试图找出最适合解决这个问题的算法。我认为使用二分匹配（最大）算法可能是我需要的。

编辑3：

感谢大家花时间提供帮助，我没有忘记答案。我不得不暂时把它放在一边，但很快我就会得到它，并且接受的答案将获得我剩余的 300 赏金。

标签： phpalgorithmoptimizationpartition-problem

解决方案

所以我测试了一个遗传算法，它可以工作。我使用了Jenetics，一个 Java 库（它不是 PHP，抱歉，但 PHP 不适合繁重的计算）。

我以1400卡路里作为每日目标。

要最小化的函数是均方误差。

这是代码：

import java.util.ArrayList;
import io.jenetics.*;
import io.jenetics.engine.*;
import io.jenetics.util.*;

public class Recipes
{
    private static final int TARGET = 1400;
    private static final int DAYS = 7;

    private static class Recipe
    {
        public int id;
        public int calories;

        public Recipe(int id, int calories)
        {
            this.id = id;
            this.calories = calories;
        }
    }

    private static ISeq<Recipe> getSeq(int[] ids, int[] calories)
    {
        ArrayList<Recipe> list = new ArrayList<>();
        for(int i=0;i<ids.length;i++)
            list.add(new Recipe(ids[i], calories[i]));
        return ISeq.of(list);
    }

    private static double meanSquareError(Genotype<EnumGene<Recipe>> gt)
    {
        int err = 0;
        for(int d=0;d<DAYS;d++)
        {
            int calories = 0;
            for(int m=0;m<3;m++)
                calories += gt.get(m).get(d).allele().calories;
            err += (calories-TARGET)*(calories-TARGET);
        }
        return err / (double)DAYS;
    }

    public static void main(String[] args)
    {
        ISeq<Recipe> recipes1 = getSeq(new int[]{ 1,  2,  3,  4,  5,  6,  7,  8,  9}, new int[]{310, 360, 450, 330, 220, 390, 400, 320, 460});
        ISeq<Recipe> recipes2 = getSeq(new int[]{10, 11, 12, 13, 14, 15, 16, 17, 18}, new int[]{420, 360, 450, 310, 320, 490, 440, 520, 560});
        ISeq<Recipe> recipes3 = getSeq(new int[]{19, 20, 21, 22, 23, 24, 25, 26, 27}, new int[]{510, 660, 750, 610, 580, 690, 710, 620, 730});

        Factory<Genotype<EnumGene<Recipe>>> gtf = Genotype.of(
            PermutationChromosome.of(recipes1, DAYS),
            PermutationChromosome.of(recipes2, DAYS),
            PermutationChromosome.of(recipes3, DAYS)
        );

        Engine<EnumGene<Recipe>, Double> engine = Engine
            .builder(Recipes::meanSquareError, gtf)
            .optimize(Optimize.MINIMUM)
            .populationSize(50)
            .alterers(new SwapMutator<>(0.2), new PartiallyMatchedCrossover<>(0.2), new Mutator<>(0.01))
            .build();

        Phenotype<EnumGene<Recipe>, Double> result = engine.stream()
            .limit(20000)
            .collect(EvolutionResult.toBestPhenotype());

        for(int m=0;m<3;m++)
        {
            for(int d=0;d<DAYS;d++)
            {
                Recipe r = result.genotype().get(m).get(d).allele();
                System.out.print(String.format("%2d (%d)  ", r.id, r.calories));
            }
            System.out.println();
        }
        System.out.println("MSE = " + result.fitness());
    }
}

遗传算法是非确定性的，因此每次都会给出不同的结果。我能得到的最佳解决方案是：

 3 (450)   4 (330)   5 (220)   2 (360)   7 (400)   1 (310)   8 (320)
16 (440)  15 (490)  17 (520)  10 (420)  13 (310)  11 (360)  14 (320)
19 (510)  23 (580)  20 (660)  26 (620)  24 (690)  27 (730)  21 (750)

MSE = 14.285714

这几乎是完美的（除了周日有 1390 卡路里外，所有日子都是 1400 卡路里）。

推荐阅读