基于递归和动态规划--解决0 1背包问题

第一种方法---递归， 时间复杂度o(2的n次方)

图片.png

思路：物品[1, 2, 3, 4] 能取得的最大价值

1.选： 若选择arr[4]，则问题变成求物品[1，2，3] 在背包容量 3（8-5）的情况下最大值 + arr[4]的值（6）

2. 不选： 则问题变成求物品[1，2，3] 在背包容量 8的情况下最大值
   ----很明显递归可以解决
   将两种情况得到的值，取最大值做为最终返回值，既 max[1选， 2不选]
   递归结束条件 当index === 0,既第一个时，若容量大于arr[0]的体积，则放进去，值加value[0], 否则返回 0（放不进去）

//递归
        function rec(vol, value, index, rest) {
            //递归边界
            if(rest ===0) return 0
            if(index === 0 && vol[0] <= rest){
                return value[0]
            }else if(index === 0){
                return 0
            }

            //剩余空间比当前物品体积小，则A 为负值，是为了让其只能走不选的情况，
            if(rest - vol[index] >= 0){
                //选
                var A = rec(vol, value, index-1 , rest - vol[index]) + value[index]
            }else {
                var A = -1
            }
            //不选
            var B = rec(vol, value, index-1, rest)
            return Math.max(A, B)
        }

动态规划问题；

其实就是填表，将之前计算过的值存起来，时间复杂度是O(n),

序 号 | 0 | 1 | 2 | 3 | 4 | 5 | 6| 7 | 8 | <=代表背包容量分别为0-8时的情况
物品0|
物品1|
物品2|
物品3|
物品4|
二维数组 [物品4] [8]是最后输出的值
填入规则如下图

图片.png

图片.png

//动态规划
        function dp(vol, value, rest) {
            if(rest === 0) return 0
           //构造二维数组
            var len = vol.length
            var opt = new Array(len+1)
            var row = new Array(rest)

            var first_row = new Array(rest+1)
            for(let i = 0; i < rest+1; i++){
                first_row[i] = 0
            }

            for(let i =0; i < opt.length; i++){
                i === 0 ? opt[i] = first_row : opt[i] = [0, ...row];
            }
          
            for(let i = 1; i < len+1; i++){
                for(let j = 1; j < rest+1; j++){
                    if(vol[i-1] > j ){
                        //背包容量不够时，取上一的最优解
                        opt[i][j] = opt[i-1][j]
                    }else {
                        //背包容量够时，A是取（考虑当前容量减去A容量，还可以                    得到的最优解），
                        //B 是不取
                        var A = value[i-1] + opt[i-1][j - vol[i-1]]
                        var B = opt[i-1][j]
                        opt[i][j] = Math.max(A, B)
                    }
                }
            }
            return opt[len][rest]
            // return opt
        }
        //vol 是物品体积
        var vol = [2,3,4,5]
        //value是物品价值
        var value = [3,4,5,6]
        var res = dp(vol, value, 8)