求优化排列组合算法（付红包）

问一下GPT吧,他最擅长这种算法

在循环次数和查询时间取一个最优解。例如将循环100次中的最优解返回，可以根据具体需求优化算法，比如减肥餐肯定要求碳水低，但又不能影响健康的前提下进行搭配。

有 在随机给他们分配克重 就没法很好的用算法了！

可以每个类按次随机，最后一个数据判断结果在不在范围内，在范围内就随机，不在就从头开始

先不说“能量、碳水化合物、脂肪、蛋白质含量各自的和相加，不超过各自的最小值和最大值”这个要求，假定每种菜品重量上限100克，就有C(4,4) * 100^4上百万种可能，这样一次性返回结果先不说耗时情况，内存怕都不够。有没有种可能直接改需求呢？像省市县三级联动一样来个四级联动，让用户分别选择菜品，重量，最后计算能量、碳水总和看是否在合适范围内？

看看动态规划算法吧

猴子排序 :joy:全看用户个人运气

有意思，感觉像变形的旅行商问题，蹲个方案。

有意思，蹲个方案。

复杂的问题简单化 直接将所有的排和组合，以及总分数，直接存储 使用的时候直接搜索就好了，存储上如果mysql支持不了，可以使用es等

给出的示例数据就有问题了，能量虽然给出的是每种菜品100g的量，但后续还列出了菜品最少搭配的克数要求，由当前给出的示例量来说，不管如何都已经无法满足能量不超300的要求,而且就目前的匹配规则来看，如果需求是必须尽可能的匹配到满足条件组合菜品的话，那这个匹配量很大，四个属性外加重量限制，一个不满足等于全部又要重新组合，但重新组合之后，原先的数据又是可以复用不能排除；感觉这种计算程度是不是安排成后台设定选择固定的菜品绑定（可多种菜品组合），然后计算不能的菜品组合来计算菜的占重，而不是使用全随机的方式进行菜品组合的计算

试了一下把全部步长生成出来之后，单独匹配四列的组合，最后再根据下标取一个成功匹配的组合，在少量的菜品数和步长数的情况下还能计算，但只要其中一种数量太大就直接爆炸，不过生成的数据不是线性增长的，线性增长数据的提前退出增多可能会快一点吧，同种情况下，JAVA好像会快点 $caiOne = [[[“id”=>1,”name”=>”名称”,”one”=>1,”two”=>1,”three”=>1,”four”=>1]]]

/**
     * 计算单列组合
     * @param string $str 单列
     * @param array $caiOne 一类菜品数据
     * @param array $caiTwo 二类菜品数据
     * @param array $caiThree 三类菜品数据
     * @param array $caiFour 四类菜品数据
     * @return array
     */
    public static function mathArrStart($str,$caiOne,$caiTwo,$caiThree,$caiFour)
    {
        /**
         * 循环同一列获取满足条件的所有菜系组合
         */
        $end = [];
        //顶层循环取菜品数最少列，可以减少循环时间  //todo
        foreach ($caiOne as $caiOneKey => $val){
            foreach ($val as $caiOneValKey => $itemOne){
                $minOne = 100 - $itemOne[$str];
                $maxOne = 300 - $itemOne[$str];
                //大于最大重量直接退出
                if ($maxOne <= 0){
                    continue;
                }
                foreach ($caiTwo as $caiTwoKey => $valTwo){
                    foreach ($valTwo as $caiTwoValKey=> $itemTwo){
                        $minTwo = $minOne - $itemTwo[$str];
                        $maxTwo = $maxOne - $itemTwo[$str];
                        //大于最大重量直接退出
                        if ($maxTwo <= 0){
                            continue;
                        }
                        foreach ($caiThree as $caiThreeKey=> $valThree){
                            foreach ($valThree as $caiThreeValKey=> $itemThree){
                                $minThree = $minTwo - $itemThree[$str];
                                $maxThree = $maxTwo - $itemThree[$str];
                                //大于最大重量直接退出
                                if ($maxThree <= 0){
                                    continue;
                                }
                                foreach ($caiFour as $caiFourKey => $valFour){
                                    foreach ($valFour as $caiFourValKey => $itemFour){
                                        //最小重量不满足，直接退出
                                        $minFour = $minThree - $itemFour[$str];
                                        if ($minFour > 0){
                                            continue;
                                        }
                                        //大于最大重量直接退出
                                        $maxFour = $maxThree - $itemFour[$str];
                                        if ($maxFour < 0){
                                            continue;
                                        }
                                        //只保留一种相同菜系组合
                                        $idx = $itemOne["id"].",".$itemTwo["id"].",".$itemThree["id"].",".$itemFour["id"];
                                        if (!isset($end[$idx])){
                                            $end[$itemOne["id"].",".$itemTwo["id"].",".$itemThree["id"].",".$itemFour["id"]] = [
                                                $minFour,$maxFour,
                                                $itemOne["name"],
                                                $itemTwo["name"],
                                                $itemThree["name"],
                                                $itemFour["name"],
                                            ];
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return $end;
    }

这个不是很典型的递归回溯算法，直接使用递归回溯的模版就可以写出来了