编 写： zhangyue
时 间： 2016-12-27
说 明： 利用背包问题解决红包使用问题
一 01背包问题
01背包问题是指在一个容量大小固定为M的背包中，装入体积和价值不同的宝石，怎么选择才能在背包中得到最大的价值。
二 动态规划
动态规划是指
通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以一种循环的方式去解决。
通常基于一个递推公式和一个或多个初始状态，当前子问题的解由上一个子问题的解推出。
有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最 好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线
状态转移方程：
d(N,M) = max(d(N-1,M), d(N-1, M-weight(i)) + value(i));
d(N,M) 有容量为M的背包，有N个宝石
d(N-1,M) 当前的宝石不放入背包,所能获取的最大价值
d(N-1, M-weight(i)) + value(i) 当前宝石放入背包，所能够获取的最大价值
三 代码
function getResult($bagItems, $bagSize) {
var result = array();
//生成状态数组
foreach ($i = 0; $i < $bagSize; $i ++) {
foreach ($j = 0; $j < count($bagItems); $j ++) {
if ($bagItems[$j]['weight'] > $i) {
//当前重量大于当前背包总重量
if (j != 0) {
$result[$j][$i] = $result[$j-1][$i];
} else {
//第一个元素 $j-1不存在，不存在前一个状态
$result[$j][$i] = 0;
}
} else {
//当前重量小于背包，可以放入背包
if ($j != 0 ) {
$tmp_value = $result[$j-1][$i - $bagItems[$j]['weight']] + $bagItems[$j]['weight'];
$result[$j][$i] = max($result[$j-1][$i], $tmp_value);
} else {
//第一个元素 $j-1不存在,不存在前一个状态
$result[$j][$i] = $bagItems[$j]['weight'];
}
}
}
}
//根据得到的状态得到所选的数组
$return = array();//存储放回的组合
$cur_size = $bagSize;//当前红包容量
for ($n = count($bagItems); $n >= 0 ; $n--) {
if ($cur_size == 0) {
break;
}
if ($n == 0 && $bagItems[$n]['weight'] < $cur_size) {
$return[] = $bagItems[$n]['id'];
break;
}
if ($bagItems[$n][$cur_size] - $bagItems[$n-1][$cur_size - $bagItems[$n]['weight']] == $bagItems[$n]['weight']) {
//判断当前的这个商品是不是在最优解里，如果不在则不放入
$return[] = $bagItems[$n]['id'];
$cur_size = $cur_size - $bagItems[$n]['weight'];
}
}
//得到结果
return $return;
}
四 递推表格
函数得到的递推表格和最终最优结果：
| 体积 | 价值 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| 4 | 4 | 0 | 0 | 0 | 0 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 |
| 5 | 5 | 0 | 0 | 0 | 0 | 4 | 5 | 5 | 5 | 5 | 9 | 9 | 9 |
| 6 | 6 | 0 | 0 | 0 | 0 | 4 | 5 | 6 | 6 | 6 | 9 | 10 | 11 |
五 红包问题
使用红包时，只需要将价值和体积都类比于红包的金额即可，这样可以选出最后得到的红包使用组合。
存在问题：
1 红包会涉及小数的问题，红包现在只保留两位小数，最简单的方法是给红包*100，这样会增加递推数组的大小，增加空间复杂度
2 红包还存在过期时间，可考虑如何加上过期时间这一条件
3 由于红包价格和体积是同一个值，可考虑简化算法