背包问题

前端算法-背包问题

最近刷LeetCode的发现最近几天的每日一题，背包问题还是蛮多，下面我将根据自己对解答方式的看法，做出的一些总结。

前言

假设我有一个背包，容量为10

如有一下物品，计算出，用容量为10的背包，怎么装才能让背包里面装入的物品，价值和为最大。

这个问题我们可以这样思考，假设我们在用背包一个一个去装水果的时候，首先装入的就是苹果。

容量为10，苹果价值为5，大小为3，装完苹果以后我们剩余的容量就只剩下了 10 – 3 = 7。

由此我们可以知道，如果我们装下苹果 那我们现在，背包的最大价值 = 背包容量为7时候的最大价值 + 苹果的价值。

背包容量为7时候的最大价值，具体指的是，水果按顺序加入时，装苹果之前的那一次，容量7时候的最大价值。然后我们继续往上推，就可以得到一个二维数组dp。

我们把背包插成 [0 – 10] 个不同的背包，然后让水果依次去装入这些不同的背包，我们先看苹果，由于苹果的大小为3，所以背包容量为 0 – 2的能装入的价值，都为0，到3以后，就能装入苹果了，因此价值为5，

当开始装入香蕉时，同理0-2，装不进去，都为0，到了3，我们装入香蕉，容量剩余 0 ，在装苹果之前，容量为0，能装入的最大价值为0，也就是dp[0][0]，此时我们装入总价值为3，但我们可以发现，容量为3时，装入苹果的价值为5，更高。

我们可以这样看，也就是比较 dp[1][3] 和 dp[0][3],谁更大，如果 dp[0][3] 更大，我们就需要将 dp[0][3] 赋值给dp[1][3]，因此得到了5，

后面依次计算，我们就可以得到dp[5][10],当所有东西都有考虑了是否装入以后，背包容量为10的时候，能装入的最大价值。

大概了解一下背包问题以后，我们来看LeetCode上面的几道实际例子。

实例

1049. 最后一块石头的重量 II

由题意我们可以得到的信息有，两块石头，相等返回0，一大一下，返回差值。如此下来，有两种情况，所有石头都相互抵消或者剩下一块，问题的核心返回最后那块石头的，最小的可能重量。

解题思路，这个问题，我们可以转化成，把石头分成两堆，这两堆石头相减，如何得到最小的差值。

假设石头总和为 sum ，两堆中其中一堆重量为 nrg， 另一堆就会等于 sum – nrg；

因此 差值 = （sum – nrg）- nrg = sum – 2nrg ，我们可以看出nrg越大，差值就会越小，当nrg = sum/2,差值就会达到最小0，因此问题的可以转化为，一个容量为sum/2的背包，在石头中，能装到的最大价值。

var lastStoneWeightII = function(stones) {
    //我们可以先算出石头的总和sum
    let sum = stones.reduce((s1,s2)=>{return s1+s2});
    //然后算出背包容量
    let nrg = Math.floor(sum/2);
    //定义二维数组dp用于记录
    let dp = new Array(stones.length+1).fill(0).map(()=>new Array(nrg+1).fill(0));
    //循环stones数组，因为stones[0] = 0,所以我们直接从1开始
    for(let i = 1;i<=stones.length;i++){
        let stone = stones[i-1];
        //循环背包容量
        for(let j = 0;j<=nrg;j++){
            //继承上一次的最大值
            dp[i][j] = dp[i-1][j];
            //判断当前背包容量，是否能将石头添加进去
            if(j>=stone){
                 //如果背包容量足够，dp[i][j]就会等于，装入石头和剩余容量能装入的最大值相加,同时和装入上一个石头时的最大值进行比较。
                dp[i][j] =Math.max(stone+dp[i-1][j-stone],dp[i][j]);
            }
        }
    }
    //最后返回sum - 2nrg;
    return sum - 2*dp[stones.length][nrg]
}
复制代码

494. 目标和

这一题和上面那一题的解题思路大致相同,区别在一个是能装的最大值，一个装满有多少种可能。

我依然可以把数组里面的值分为两半，我们设负的那一半为nrg，数组总和为sum，正的一半为sum – nrg

我们可以得出 target = (sum – nrg) – nrg = sum – 2nrg，nrg = （sum – k）/ 2。这个时候我们只要求出装满容量为nrg的背包，有多少种可能。

如果target>sum，相当于nums的总数还没有target大，那就不可能有方法得到target。
如果(sum – k)/2是一个小数，也不符合情况，这是一个整数数组，nrg一定是个整数。

因为在背包容量为0的时候，装满背包只有一种情况那就是不装，所以定义为dp[0][0] = 1;

var findTargetSumWays = function(nums, target) {
    //求出总数sum
    let sum = nums.reduce((s1,s2)=>{return s1+s2});
    //先算出差值用于判断
    let diff = sum - target;
    //如果target>sum || 或者diff%2 ！== 0 
    if(diff<0 || diff%2 !==0){
       return 0
    }
    let nrg = diff/2;
    //定义dp二维数组，存储状态
    let dp = new Array(nums.length+1).fill(0).map(()=>new Array(nrg+1).fill(0));
    //定义初始状态
    dp[0][0] = 1;
    for(let i = 1;i<=nums.length;i++){
        let num = nums[i-1];
        for(let j = 0;j<=nrg;j++){
            dp[i][j] = dp[i-1][j];
            if(j>=num){
                //不选num的可能性+选num的可能性
                dp[i][j]+=dp[i-1][j-num];
            }
        }
    }
    return dp[nums.length][nrg]
}
复制代码

优化

在上面那个问题中，我们可以发现，我们只用到了i（当前这一次的循环），i-1(上一次的循环）

dp[i][j] = dp[i-1][j] + dp[i-1][j-num]

如果这个时候，我们将nrg的循环进行倒叙，即j = nrg;j>=num;j–

改成这一步，我们可以很明显的看出，满足了j>=num的这种条件

因为是逆着循环的，所以我们可以这样理解

假设我们这个时候，我们循环到了i和j，设置一个一维数组，dp = new Array(nrg+1).fill(0)。

就会得到一个等式 dp[j] = dp[j]+dp[j – num[i-1]]

此刻我们循环进来的数是 i ，我们要去循环背包容量，判断装不装 i。

因为我们是逆着循环的，所有 dp[j]+dp[j – num[i-1]] 中的的dp[j]实际上是没有计算装不装i的可能性，也就是 i – 1,同理j – num[i-1]，是位于d[j]之前的，也没有进行计算，所以也是 i – 1进来时的计算结果。

优化一下便可以得到下面的方法

var findTargetSumWays = function(nums, target) {
    //求出总数sum
    let sum = nums.reduce((s1,s2)=>{return s1+s2});
    //先算出差值用于判断
    let diff = sum - target;
    //如果target>sum || 或者diff%2 ！== 0 
    if(diff<0 || diff%2 !==0){
       return 0
    }
    let nrg = diff/2;
    //定义dp
    let dp = new Array(nrg+1).fill(0);
    //定义初始状态
    dp[0] = 1;
    for(let i = 1;i<=nums.length;i++){
        let num = nums[i-1];
        for(let j = nrg;j>=num;j--){
           dp[j] = dp[j]+dp[j - num]
        }
    }
    return dp[nrg]
}
复制代码