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

背包问题:有一个背包，容量为4磅，现有如下物品；

要求装入的物品不能重复；
要求达到的目标为装入的背包的总价值最大，并且重量不超出；

物品	重量	价格
吉他	1	1500
音箱	4	3000
电脑	3	2000

动态规划的原理

动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。

最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。

解决过程

每次遍历到的第i个物品,根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的num个物品，设v[i]、w[i]分别为第i个物品的价值和重量，m为背包的容量,再令v[i][j]表示在前i个物品中能够装入容量为j的背包中的最大价值

寻找递推关系式，面对当前商品有两种可能性：

包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛V(i-1,j)，V(i-1,j-w(i))+v(i)｝。

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)，但价值增加了v(i)；

递推关系式：

v[i][0]=v[0][j]=0; //表示填入表第一行和第一列是 0
当 w[i]> j 时:v[i][j]=v[i-1][j] //当准备加入新增的商品的容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
当 j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]} //当准备加入的新增的商品的容量小于等于当前背包的容量

装入的方式:

v[i-1][j]: 就是上一个单元格的装入的最大值
v[i]: 表示当前商品的价值
v[i-1][j-w[i]]: 装入i-1商品，到剩余空间j-w[i]的最大值,[装入之前是什么状态，肯定是V(i-1,j-w(i))],由于最优性原理（上文讲到），V(i-1,j-w(i))就是前面决策造成的一种状态，后面的决策就要构成最优策略。两种情况进行比较，得出最优
j>=w[i]时: v[i][j]=max{v[i-1][j], v[i]+v[i-1][j-w[i]]}

图解背包

商品

物品	重量	价格
吉他	1	1500
音箱	4	3000
电脑	3	2000

填图

物品	1磅	2磅	3磅	4磅
0	0	0	0	0
吉他	1500	1500	1500	1500
音箱	1500	1500	1500	3000
电脑	1500	1500	2000	2000+1500

代码实现

class KnapsackProblem 
{
    function __construct()
    {
        $this->knapSack();
    }

    function knapSack()
    {
        //重量
        $w = [1, 4, 3];
        //价值
        $bagV = [1500, 3000, 2000];
        //背包容量
        $m = 4;
        //物品的个数
        $num = count($bagV);

        //初始化将第一列第一列设置为0
        $v[0] = array_fill(0, 5, 0); 
        for ($j = 0; $j < 4; $j++) {
            $v[$j][0] = 0;
        }

        for ($i = 1; $i < count($v); $i++) {
            for ($j = 1; $j < count($v[0]); $j++) {
                if ($w[$i-1] > $j) {
                    $v[$i][$j] = $v[$i-1][$j];
                } else {
                    if ($v[$i-1][$j] < $bagV[$i-1] + $v[$i-1][$j-$w[$i-1]]) {
                        $v[$i][$j] = $bagV[$i-1] + $v[$i-1][$j-$w[$i-1]];
                        $path[$i][$j] = 1;
                    } else {
                        $v[$i][$j] = $v[$i-1][$j];
                    }
                }
            }
        }
        $this->showGoods($v);
        $this->showBagGoods($path, $w);
    }

    function showGoods($v)
    {
        for ($i = 0; $i < count($v); $i++) {
            for ($j = 0; $j < count($v[$i]); $j++) { 
                print($v[$i][$j].'===>');
            }
            echo PHP_EOL;
        }
    }

    function showBagGoods($path, $w)
    {
        //行最大下标
        $i = count($path);
        //列最大下标
        $j = count($path[1]);
        //从path最后开始遍历
        while ($i > 0 && $j > 0) {
            if (isset($path[$i][$j]) && $path[$i][$j] == 1) {
                printf("第%d个商品放入到背包\n", $i);
                $j -= $w[$i-1];
            }
            $i--;
        }
    }
}

new KnapsackProblem();

结果：

0===>0===>0===>0===>0===>
0===>1500===>1500===>1500===>1500===>
0===>1500===>1500===>1500===>3000===>
0===>1500===>1500===>2000===>3500===>
第3个商品放入到背包
第1个商品放入到背包