登录  /  注册

PHP实现动态规划之背包问题

藏色散人
发布: 2019-08-13 14:22:17
转载
3256人浏览过

事情原由

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

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。

如何选择最合适的物品放置于给定背包中,与我们的题目相符合,所以这次我们使用的是“0-1背包问题”,用我们这次的题目进行代入,“总人数” 等价于 “背包”,“物品” 等价于 “工单类型”,物品的重量就是所需人数。

补充:

背包问题解法延伸问题有三个:无界背包问题、0-1背包问题、二次背包问题 (不做详细延伸,只需我们使用的)

算法题目如下

554d7665af17098d4155de2f5b06828.png

动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。动态规划的设计都有着一定的模式,一般要经历以下几个步骤。

初始状态→│决策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]) ==> 用减去当前工单所需人数,在上一个决策中对应人数的利润

be7a62a09daa68f67d877284464c11e.png

所以最优解的答案是:决策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[&#39;carDetail&#39;] as $val) {
            // 初始化各个套餐:所需人数、利润和套餐名称数组
            $peopleArr[] = $val[&#39;technician&#39;];
            $gainArr[] = $val[&#39;amount&#39;];
            $nameArr[] = $val[&#39;type&#39;];
        }
        // 获取人数总数(背包)
        $totalPeople = $postData[&#39;people&#39;];
        // 做检测单数
        $items = count($peopleArr);
        // 利润列表 - 初始状态
        $cacheMap[] = array_fill(1, $items, 0);
        // 套餐列表 - 初始状态
        $cacheMapName[] = array_fill(1, $items, &#39;&#39;);
        //中间的各种决策(依次放入物品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 = &#39;&#39;;
                    }
                    $nowTotalGain = $gain + $surplusGain;
                    $cacheMap[$j][$i] = max($prevGain, $nowTotalGain);
                    if ($prevGain > $nowTotalGain) {
                        $cacheMapName[$j][$i] = $prevName;
                    }else{
                        $cacheMapName[$j][$i] = $name.&#39;+&#39;.$surplusName;
                    }
                }
            }
        }
        $actual = count($postData[&#39;carDetail&#39;]);
        return [
            &#39;maxMatch&#39; => $cacheMap[$actual][$totalPeople],
            &#39;maxMatchName&#39; => trim($cacheMapName[$actual][$totalPeople],&#39;+&#39;)
        ];
    }
}
$bestMatch = new bestMatch;
if (empty($_POST) || isset($_POST[&#39;people&#39;]) && $_POST[&#39;people&#39;] > 0) {
    die(&#39;提交参数有误&#39;);
}
$res = $bestMatch->getMethod($_POST);
$t2 = microtime(true);
echo &#39;动态规划: &#39;.&#39;<br/>&#39;;
echo &#39;最佳金额: &#39;.$res[&#39;maxMatch&#39;].&#39;<br/>&#39;;
echo &#39;最佳套餐搭配: &#39;.$res[&#39;maxMatchName&#39;].&#39;<br/>&#39;;
echo &#39;耗时&#39;.round($t2-$t1,7).&#39;秒&#39;.&#39;<br/>&#39; ;
echo &#39;消耗内存: &#39; . memory_get_usage().&#39;字节&#39;.&#39;<br/>&#39; ;
登录后复制

解答方式二:递归

<?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[&#39;name&#39;] = $up[&#39;name&#39;].&#39;+&#39;.$array[$i][&#39;type&#39;];
                $value[&#39;amount&#39;] = bcadd($up[&#39;amount&#39;],$array[$i][&#39;amount&#39;]);
                $value[&#39;technician&#39;] = bcadd($up[&#39;technician&#39;],$array[$i][&#39;technician&#39;]);
            }else{
                $value[&#39;name&#39;] = $array[$i][&#39;type&#39;];
                $value[&#39;amount&#39;] = bcadd($array[$i][&#39;amount&#39;],0);
                $value[&#39;technician&#39;] = bcadd($array[$i][&#39;technician&#39;],0);
            }
            $result[]  = $value;
            $this->getSortList($array,$i+1,$value,$result);
        }
        return $result ;
    }
    public function getMethod($postData)
    {
        $people = $postData[&#39;people&#39;];
        $carDetail = $postData[&#39;carDetail&#39;];
        $allResult = $this->getSortList($carDetail);
        $bestMatch = [];
        foreach ($allResult as $val) {
            if ($val[&#39;technician&#39;] <= $people) {
                if ($bestMatch) {
                    if ($val[&#39;amount&#39;] > $bestMatch[&#39;amount&#39;]) {
                        $bestMatch = $val;
                    }
                }else{
                    $bestMatch = $val;
                }
            }
        }
        return $bestMatch;
    }
}
$optimal = new optimal();
if (empty($_POST) || isset($_POST[&#39;people&#39;]) && $_POST[&#39;people&#39;] > 0) {
    die(&#39;提交参数有误&#39;);
}
$bestMatch = $optimal->getMethod($_POST);
$t2 = microtime(true);
echo &#39;递归查询: &#39;.&#39;<br/>&#39;;
echo &#39;最佳金额: &#39;.$bestMatch[&#39;amount&#39;].&#39;<br/>&#39;;
echo &#39;最佳套餐搭配: &#39;.$bestMatch[&#39;name&#39;].&#39;<br/>&#39;;
echo &#39;耗时&#39;.round($t2-$t1,7).&#39;秒&#39;.&#39;<br/>&#39; ;
echo &#39;消耗内存: &#39; . memory_get_usage().&#39;字节&#39;.&#39;<br/>&#39; ;
登录后复制

以上就是PHP实现动态规划之背包问题的详细内容,更多请关注php中文网其它相关文章!

智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
相关标签:
来源:juejin网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号