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 由于红包价格和体积是同一个值，可考虑简化算法

发表评论