01背包理论基础

01背包

01背包：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是values[i]。每件物品只能使用一次，求解将哪些物品装入背包里物品价值总和最大。

二维dp数组01背包

1.确定dp数组及其下标含义

对于背包问题，有一种写法：使用二维数组，即dp[i] [j]表示从下标为[0-i]的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

即i为下标，j为容量。

2.确定递推公式

不放物品：由dp[i-1] [j]推出，里面不放物品i的最大价值，此时dp[i] [j]就是dp[i-1] [j] (就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)
放物品i：由dp[i-1] [j-weight[i]]推出，dp[i-1] [j-weight[i]]为背包容量是j-weight[i]的时候不放物品i的最大价值，那么dp[i-1] [j-weight[i] ] + value[i]（物品i的价值），就是背包放物品i得到的最大价值。

所以递归公式： dp[i] [j] = max(dp[i-1] [j], dp[i-1] [j-weight[i]]+value[i])

3.dp数组初始化

从dp[i] [j] 的定义出发，如果背包容量j为0的话，即dp[i] [0]，无论选取哪些物品，背包价值总和一定为0.

dp[0] [j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。

当 j < weight[0]的时候，dp[0] [j]应该是0，因为背包容量比编号0的物品重量还小。

当 j > weight[0]的时候，dp[0] [j]应该是value[0]，因为背包容量足够放编号0的物品。

4.确定遍历顺序

先遍历物品和先遍历背包重量都可以。

先遍历物品，物品从第一个开始（没有第0个）：

如果j<weight[i]，说明放不下，则与上一个结果相同、

如果j>=weight[i]，说明放得下，比较添加前和添加后哪个更合适。

// weight数组的大小 就是物品个数
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

先遍历背包，再遍历物品，也是可以的！（注意我这里使用的二维dp数组）

例如这样：

// weight数组的大小 就是物品个数
for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
    for(int i = 1; i < weight.size(); i++) { // 遍历物品
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

5.举例推导

…

01背包基础理论（滚动数组）

一维数组

对于背包问题其实状态都是可以压缩的。

二维数组递推公式：dp[i] [j] = max(dp[i-1] [j] ,dp[i-1] [j - weight[i]]+value[i]);

可以发现如果把dp[i-1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i] [j] = max(dp[i] [j] ,dp[i ] [j-weight[i]] + value[i])

与其把dp[i-1]那一层靠别到dp[i]上，不如只用一个一维数组：只用dp[j]（也可以理解为滚动数组）

滚动数组：上一层可以重复利用，直接拷贝到当前层。

dp[i] [j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

五部曲分析：

1.确定dp数组的定义

在一维dp数组中，dp[i]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

2.一维dp数组的递推公式

dp[j]为容量为j的背包所背的最大价值。

dp[j]可以通过dp[j - weight[i]]推导出来，dp[j- weight[i]]表示容量为j - weight[i]的背包所背的最大价值。

dp[j - weight[i]] + value[i]表示容量为 j - 物品i重量的背包加上物品i的价值（也就是容量为j的背包，放入物品i了之后的价值即：dp[j])

此时dp[i] 有两个选择，一个是取自己dp[j] 相当于二维dp数组中的dp[i-1] [j]，即不放回物品i，一个是取dp[i -weight[i]] +value[i]，即放入物品i，取最大的求最大价值。

因此，递推公式为：dp[j] = max(dp[j],dp[j - weight[i]] + value[i])

3.一维dp数组如何初始化

关于初始化：一定要和dp数组的定义吻合，否则到递推公式的时候就会越来越乱。

dp[j]表示：容量为j的背包。

那么、dp[0]就是0，背包容量为0所背的物品的最大值是0

那么、非零的下标：dp数组在推导的时候一定要取价值最大的数，如果题目给的价值都是正整数那么非0下标都初始化为0就可以了。

这样才能让dp数组在递归公式的过程中取最大的价值，而不是被初始值覆盖了。

假设物品价值都是大于0的，所以dp数组初始化的时候，都初始化为0就可以了。

4.一维dp数组遍历顺序

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

遍历背包的顺序是不一样的！

二维dp遍历的时候，背包容量都是从大到小，而一维dp遍历的时候，背包都是从大到小。

倒序遍历是为了保证物品i只被放入一次。->(正序赋值的话，后面的数组会重复使用前面的值，造成多次放入)

并且一维数组遍历顺序是遍历物品->再嵌套到背包容量

背包容量首先要倒序遍历、如果先遍历背包容量再嵌套物品的话，那么每个dp就只会放入一个物品。

5.举例推导dp数组

…（偷懒xixi

总结

那什么时候用一维，什么时候用二维捏。

分割等和子集

文章：13. 分割等和子集

题目：416. 分割等和子集

【思路】

这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

=》那么只要找到集合里面能够出现sum/2的子集总和，就算是可以分割成两个相同元素和子集了。

背包问题

有N件物品和一个最多能背重量为W的背包，第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

01背包

需要注意题目描述总商品是不是可以重复放入。

=》一个商品如果可以重复多次放入 = 完全背包

=》只能放入一次 = 01背包

本题，我们的元素只能放入一次，也就是使用01背包。

背包的体积为sum/2
背包要放入的商品（集合里的元素）重量为元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为sum/2的子集
背包中每一个元素是不可重复放入的。

动规五部曲：

1.确定dp数组及其下标含义

dp[i]：容量为i的背包，所能容纳物品的最大价值为dp[i]，而本题重量是数值、价值也是数值。

2.确定递推公式

01背包的递归公式：dp[j] = max(dp[j] ,dp[j - weight[i]] + value[i])

本题： dp[j] = max(dp[j] , dp[j - nums[i]] + nums[i])

3.确定数组初始化

dp[0] 一定是0，因为重量为0的时候，能装的最大价值一定是0

且题目给的价值都是正整数，非0下标初始化为0即可。

4.确定遍历顺序

使用01背包，则需要物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍布。

5.举例推导

Java实现

class Solution {
    public boolean canPartition(int[] nums) {
        int sum =0;
        for(int i : nums){
            sum += i;
        }
        if(sum %2 == 1)return false;
        int target = sum /2;
        int[] dp = new int[target+1];
        for(int i = 0;i < nums.length;i++){
            for(int j = target;j>=nums[i];j--){
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
            if(dp[target] == target){
                return true;
            }
        }

        return dp[target] == target;
    }
}

Go实现

func canPartition(nums []int) bool {
    sum := 0
    //这里忘记下标和数值是一起遍历的了！！忘记加_,了！
    for _,i:= range nums{
        sum +=i
    }
    if sum %2 ==1 {
        return false
    }
    target := sum/2
    dp := make([]int,target+1)
    for i:=0;i<len(nums);i++{
        for j := target ; j >= nums[i]; j--{
            dp[j] = max(dp[j],dp[j-nums[i]]+nums[i])
        } 
        if dp[target] == target{
            return true
        }
    }
    return dp[target] == target
}
func max(a , b int )int{
    if a > b{
        return a
    }
    return b
}

【算法总结】

分割等和子集：使用01背包，倒序遍历，将nums[i]看作背包的重量以及物品的价值！

【语言总结】

忘记语言特性？有几天没用就不熟悉了。还是不够熟练泥。

//这里忘记下标和数值是一起遍历的了！！忘记加_,了！
for _,i:= range nums{
    sum +=i
}