问题：一共有N件物品，第i（i从1开始）件物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
通常遇到这种问题最容易想到的是暴力递归的方式

暴力递归

如果使用暴利递归的方式一般把该问题拆解成两步，然后递归调用：

既然是有n件物品，我们编上号从0~i，那么对于第i个商品就有如下两种可能：
1、第i件商品被选用了；
2、第i件商品没被选用

//采用暴利递归的方式
 class func beibaoQuestion(v:[Int],w:[Int],maxWeight:Int) -> Int{
      //边界条件判断
        if v.count != w.count || v.count == 0 {
            return 0
        }
        return process(v: v, w: w, index: 0, rest: maxWeight)
    }
    //递归过程
    class func process(v:[Int],w:[Int],index:Int,rest:Int) -> Int{
        //如果超过最大背包容量，那么我就要告诉我的前一步递归者，我已经超出容量了
        if rest < 0 {
            return -1
        }
        if index == v.count {
            return 0
        }
        
        //第index号商品我不要
        let p1 = process(v: v, w: w, index: (index + 1), rest: rest)
        
        //第index号商品我要
        //第index之后的商品最大价值为：
        var p2:Int = 0
        let next = process(v: v, w: w, index: (index + 1), rest: rest - w[index])

      /**
         最大容量如果是15
         编号  0  1  2  3   4
         v    3  1  4  7   3
         w    5  6  3  19  12
         
              不 不 不  要
         
         如上表所示，加入在走到编号3的位置时，如果要这个商品，那么再次递归的时候，剩余的背包重量将会是15-（5+6+3）- 19 < 0
         也就是说，如果选择了该index号商品，就会导致背包容量直接爆表，所以这个商品是无效的
         */
        //对于超出容量的处理
        if next != -1 {
            p2 = v[index] + next
        }
        print(p2)
        return p1 > p2 ? p1 : p2
    }

采用暴利递归的方式可以发现，其时间复杂度为O(2^N)，数据量越大，递归时间越长；
下面改为动态规划的方式：

class func beibaoQuestion2(v:[Int],w:[Int],maxWeight:Int) -> Int{
        if v.count != w.count || v.count == 0 {
            return 0
        }
        //由暴力递归的过程可以发现，v和w是固定的参数，只有索引位置index和剩余背包容量rest为变化项，所以构建bp表也是根据这两个来创建；
        /**
         最大容量如果是15
         编号  0  1  2  3   4
         v    3  1  4  7   3
         w    5  6  3  19  12
        |
        改成bp表
         
         重量变化范围    -1       0   1  2   3   4   5   6   7   8   9   10  11  12  13  14  15
         
                            0
                            1
                            2
                            3
                            4
                            5
         
         根据递归过程发现
         if index == v.count {
             return 0
         }
         当index与物体数量+1相等时返回的都是0
         所以第length位置的容量都为0
         **/
        
        
        
        let length = v.count
        var dp:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: (maxWeight + 1)), count: (length + 1))
        
        for index in (0..<length).reversed() {
            for rest in (0...maxWeight) {

                let p1 = dp[index + 1][rest]
   
                var p2:Int = 0
                let next = (rest - w[index]) < 0 ? -1 : dp[index + 1][(rest - w[index])]
                if next != -1 {
                    p2 = v[index] + next
                }
                print(p2)
                dp[index][rest] = (p1 > p2 ? p1 : p2)
            }
        }
        return dp[0][maxWeight]
    }

这种方式的动态规划时间复杂度为O(n*W),空间复杂度也为O(n*W)