旗下导航:搜·么
当前位置:网站首页 > PHP教程 > 正文

PHP完成动态计划之背包题目【php教程】

作者:搜搜PHP网发布时间:2019-11-26分类:PHP教程浏览:107


导读:事变缘由因为我司举行一个算法编程大赛,随机抽签下面图片的算法题目,想了一段时间记起之前在书(算法图解)上有一个算法比较相符,那就是动态计划中的“背包题目”。背包题目(K...
事变缘由

因为我司举行一个算法编程大赛,随机抽签下面图片的算法题目,想了一段时间记起之前在书(算法图解)上有一个算法比较相符,那就是动态计划中的“背包题目”。

背包题目(Knapsack problem)是一种组合优化的NP完全题目。题目能够形貌为:给定一组物品,每种物品都有本身的分量和价钱,在限制的总分量内,我们怎样挑选,才使得物品的总价钱最高。

怎样挑选最合适的物品放置于给定背包中,与我们的题目相相符,所以此次我们运用的是“0-1背包题目”,用我们此次的题目举行代入,“总人数” 等价于 “背包”,“物品” 等价于 “工单范例”,物品的分量就是所需人数。

补充:

背包题目解法延长题目有三个:无界背包题目、0-1背包题目、二次背包题目 (不做细致延长,只需我们运用的)

算法题目以下

动态计划所处置惩罚的题目是一个多阶段决议计划题目,平常由初始状况最先,经由历程对中心阶段决议计划的挑选,到达完毕状况。这些决议计划形成了一个决议计划序列,同时肯定了完成全部历程的一条运动线路(通常是求最优的运动线路)。动态计划的设想都有着肯定的形式,平常要阅历以下几个步骤。

初始状况→│决议计划1│→│决议计划2│→…→│决议计划n│→完毕状况

动态计划解题公式:

f(n,m)=max{f(n-1,m),f(n-1,m-w[n])+P(n,m)}

● 横向m(总人数),纵向n(4辆车做的工单范例)

● f(n-1,m) ==> (决议计划1)上一个工单范例对应的技师人数,做的工单利润

● P(n,m) ==> (决议计划2)当前工单范例对应的技师人数,做的工单利润

● f(n-1,m-w[n]) ==> 用减去当前工单所需人数,在上一个决议计划中对应人数的利润

所以最优解的答案是:决议计划n中五个技师中对应的值,1799元

PostMan提交参数:

people:5
carDetail[0][technician]:2
carDetail[0][amount]:49
carDetail[0][type]:全车安检
carDetail[1][technician]:2
carDetail[1][amount]:499
carDetail[1][type]:深度诊断
carDetail[2][technician]:3
carDetail[2][amount]:1300
carDetail[2][type]:二手车检测
carDetail[3][technician]:1
carDetail[3][amount]:10
carDetail[3][type]:空调专项检测

解答体式格局一:动态计划

<?php
// 动态计划
error_reporting(E_ALL ^ E_NOTICE);
$t1 = microtime(true);
class bestMatch
{
    public function getMethod($postData)
    {
        $peopleArr = $gainArr = $nameArr = [0];
        foreach ($postData['carDetail'] as $val) {
            // 初始化各个套餐:所需人数、利润和套餐称号数组
            $peopleArr[] = $val['technician'];
            $gainArr[] = $val['amount'];
            $nameArr[] = $val['type'];
        }
        // 猎取人数总数(背包)
        $totalPeople = $postData['people'];
        // 做检测单数
        $items = count($peopleArr);
        // 利润列表 - 初始状况
        $cacheMap[] = array_fill(1, $items, 0);
        // 套餐列表 - 初始状况
        $cacheMapName[] = array_fill(1, $items, '');
        //中心的种种决议计划(顺次放入物品a,b,c,d,e)
        // 第一个轮回是总人数
        for($i = 1; $i <= $totalPeople; $i++)
        {
            // 第二个轮回是套餐
            for($j = 1; $j < $items; $j++)
            {
                $requiredPeople = $peopleArr[$j];
                $gain = $gainArr[$j];
                $name = $nameArr[$j];
                // 上一行坐标数
                $preLine = $j-1;
                $prevGain = $cacheMap[$preLine][$i];
                $prevName = $cacheMapName[$preLine][$i];
                if($requiredPeople > $i)
                {
                    $cacheMap[$j][$i] = $prevGain;
                    $cacheMapName[$j][$i] = $prevName;
                }
                else
                {
                    // 剩余价值
                    if ($i-$requiredPeople >= 0) {
                        $surplusPeople = $i-$requiredPeople;
                        $surplusGain = $cacheMap[$preLine][$surplusPeople];
                        $surplusName = $cacheMapName[$preLine][$surplusPeople];
                    }else {
                        $surplusGain = 0;
                        $surplusName = '';
                    }
                    $nowTotalGain = $gain + $surplusGain;
                    $cacheMap[$j][$i] = max($prevGain, $nowTotalGain);
                    if ($prevGain > $nowTotalGain) {
                        $cacheMapName[$j][$i] = $prevName;
                    }else{
                        $cacheMapName[$j][$i] = $name.'+'.$surplusName;
                    }
                }
            }
        }
        $actual = count($postData['carDetail']);
        return [
            'maxMatch' => $cacheMap[$actual][$totalPeople],
            'maxMatchName' => trim($cacheMapName[$actual][$totalPeople],'+')
        ];
    }
}
$bestMatch = new bestMatch;
if (empty($_POST) || isset($_POST['people']) && $_POST['people'] > 0) {
    die('提交参数有误');
}
$res = $bestMatch->getMethod($_POST);
$t2 = microtime(true);
echo '动态计划: '.'<br/>';
echo '最好金额: '.$res['maxMatch'].'<br/>';
echo '最好套餐搭配: '.$res['maxMatchName'].'<br/>';
echo '耗时'.round($t2-$t1,7).'秒'.'<br/>' ;
echo '斲丧内存: ' . memory_get_usage().'字节'.'<br/>' ;

解答体式格局二:递归

<?php
// 递归查询
error_reporting(E_ALL ^ E_NOTICE);
$t1 = microtime(true);
class optimal
{
    public function getSortList($array,$index = 0,$up =0,&$result =[])
    {
        for ($i=$index; $i < count($array); $i++) {
            if($index > 0 ){
                $value['name'] = $up['name'].'+'.$array[$i]['type'];
                $value['amount'] = bcadd($up['amount'],$array[$i]['amount']);
                $value['technician'] = bcadd($up['technician'],$array[$i]['technician']);
            }else{
                $value['name'] = $array[$i]['type'];
                $value['amount'] = bcadd($array[$i]['amount'],0);
                $value['technician'] = bcadd($array[$i]['technician'],0);
            }
            $result[]  = $value;
            $this->getSortList($array,$i+1,$value,$result);
        }
        return $result ;
    }
    public function getMethod($postData)
    {
        $people = $postData['people'];
        $carDetail = $postData['carDetail'];
        $allResult = $this->getSortList($carDetail);
        $bestMatch = [];
        foreach ($allResult as $val) {
            if ($val['technician'] <= $people) {
                if ($bestMatch) {
                    if ($val['amount'] > $bestMatch['amount']) {
                        $bestMatch = $val;
                    }
                }else{
                    $bestMatch = $val;
                }
            }
        }
        return $bestMatch;
    }
}
$optimal = new optimal();
if (empty($_POST) || isset($_POST['people']) && $_POST['people'] > 0) {
    die('提交参数有误');
}
$bestMatch = $optimal->getMethod($_POST);
$t2 = microtime(true);
echo '递归查询: '.'<br/>';
echo '最好金额: '.$bestMatch['amount'].'<br/>';
echo '最好套餐搭配: '.$bestMatch['name'].'<br/>';
echo '耗时'.round($t2-$t1,7).'秒'.'<br/>' ;
echo '斲丧内存: ' . memory_get_usage().'字节'.'<br/>' ;

以上就是PHP完成动态计划之背包题目的细致内容,更多请关注ki4网别的相干文章!

标签:PHP