最近在做一个小需求，每笔订单会根据金额决定用户可以使用的红包最大值，如果用户选择使用红包，需要帮助用户从拥有的红包列表里选取最优的红包组合，要求组合出的红包值最接近或等于可以使用的红包最大值。后面思考了一圈，这不就是 『0-1背包问题』么，终于可以把以前学过的 『动态规划』 算法拿来实战一下了！
动态规划是什么
动态规划 (Dynamic programming 简写：DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
动态规划适用场景
一般使用动态规划来解决求最优解的问题。在解决问题的过程中需要多次决策，而每次决策都有产生一组状态，然后从最优的决策中继续下一次的决策，最终找到最优的结果。
另外动态规划还具有3个特征，如下：
最优子结构性质
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。从而我们可以通过子问题的最优解，推导出问题的最优解，也可以理解为后面阶段的状态可以通过前面阶段的状态推导出来。
无后效性
即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
可以简单理解为 在推导后面阶段状态的时候，我们只需要关心它前一阶段的状态状态，不用去关心这个状态是怎么一步步推导出来的。第二个含义就是某个阶段的状态一旦确定下来，就不会受之后阶段的决策影响。
子问题重叠性质
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次
0-1背包问题
上面的理论比较抽象，和扯犊子一样的，来看下经典的背包问题。
假设现在有5个物品他们的重量分别是 2, 2, 5, 11, 4, 现在有一个背包，能承受的最大重量是 10，请选择合适的物品放入背包，那么能组合出的物品最大重量是多少?
不同的物品组合会有多种不同的状态，我们可以使用 f(i, w) 来表示一种状态，其中 i = index 表示第几个物品， w = weight 表示当前的总重量。
整个问题的求解需要经过 『n』 个阶段，每个阶段都需要决策一个物品是否放入背包，决策的结果只有2种 『放入』 或者 『不放入』。在决策完一个物品后，背包中的物品重量会有很多种不同的状态，我们需要把每一层的 重复状态 合并，然后只留下不同的状态。然后基于上一层的状态结果来推导出下一层的状态结果。最终全部物品决策完就可以找到最优的组合解。
第0（其实也就是第一个物品，按照习惯从0开始下标吧）个物品的重量是2，然后开始决策是否放入背包，结果只有2种。如果放入背包那么此时背包的重量就是2，如果不放入背包那么背包的重量就是0.记作 $本文来源gaodaimacom搞#^代%!码&网*
搞代gaodaima码
status[0][0] = true; 和 $status[0][2] = true; 和上面的 f(i, w) 一样，前一位表示物品，后一位表示重量。
转载请注明原文链接：详解PHP怎么使用动态规划实现最优红包组合
