PHP implements dynamic programming knapsack problem

The reason for the incident

Because our company held an algorithm programming competition, the algorithm questions in the picture below were randomly drawn. After thinking about it for a while, I remembered that there was one in the book (Algorithm Illustration). The algorithm is more consistent with the "knapsack problem" in dynamic programming.

The knapsack problem is an NP-complete problem of combinatorial optimization. The problem can be described as: given a set of items, each item has its own weight and price, within the limited total weight, how do we choose so that the total price of the items is the highest.

How to choose the most appropriate items to place in a given backpack is consistent with our question, so this time we use the "0-1 backpack problem" and use our question this time to substitute it. "Total number of people" is equivalent to "backpack", "item" is equivalent to "work order type", and the weight of the item is the number of people required.

Supplement:

There are three extension problems of the solution to the knapsack problem: unbounded knapsack problem, 0-1 knapsack problem, and quadratic knapsack problem (without detailed extension, just We use)

The algorithm topic is as follows

The problem dealt with by dynamic programming is a multi-stage decision-making problem, generally starting from the initial The state starts and reaches the end state through the selection of decisions in the intermediate stages. These decisions form a decision sequence and determine an activity route to complete the entire process (usually the optimal activity route). The design of dynamic programming has a certain pattern, which generally involves the following steps.

Initial state→│Decision 1│→│Decision 2│→...→│Decisionｎ│→End state

Dynamic programming problem-solving formula:

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

● Horizontal m (total number of people), vertical n (type of work order made by 4 vehicles)

● f(n-1,m) ==> (Decision 1) The number of technicians corresponding to the previous work order type, and the profit of the work order

● P(n,m) ==> (Decision 2) The number of technicians corresponding to the current work order type, and the work done Single profit

● f(n-1,m-w[n]) ==> By subtracting the number of people required for the current work order, the profit for the corresponding number of people in the previous decision

So the answer to the optimal solution is: the corresponding value among the five technicians in decision n, 1799 yuan

PostMan submitted parameters:

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]:空调专项检测

Solution one: dynamic programming

<?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; ;

Solution two: recursion

<?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; ;

The above is the detailed content of PHP implements dynamic programming knapsack problem. For more information, please follow other related articles on the PHP Chinese website!