01背包问题基础

编 写: 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 表格是从上到下,即4-6,从左到右,即0-11生成的 2 第一行的意思:代表在0-11的背包容量下,只有一个体积为4价值为4的宝石时,所能获得最大容量 3 第二行的意思:代表在0-11的背包容量下,有一个体积为4价值为4和体积为5价值为5的两块宝石时,所能获得最大容量 4 第三行的意思:代表在0-11的背包容量下,有一个体积为4价值为4,体积为5价值为5,体积为6价值为6的三块宝石时,所能获得最大容量 5 最终结果:[6,11] = 11 这个最优解。

五 红包问题

使用红包时,只需要将价值和体积都类比于红包的金额即可,这样可以选出最后得到的红包使用组合。
存在问题:
    1 红包会涉及小数的问题,红包现在只保留两位小数,最简单的方法是给红包*100,这样会增加递推数组的大小,增加空间复杂度
    2 红包还存在过期时间,可考虑如何加上过期时间这一条件
    3 由于红包价格和体积是同一个值,可考虑简化算法

发表评论