动态规划-- 背包问题

背包

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

思路

每一件物品其实只有两个状态，取或者不取，所以可以使用回溯法搜索出所有的情况，那么时间复杂度就是o(2^n)，这里的n表示物品数量。
以暴力的解法是指数级别的时间复杂度。进而才需要动态规划的解法来进行优化！

1.确定dp数组以及下标的含义
dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。
2.确定递推公式
两个方向推出来dp[i][j]，
不放物品i：由dp[i - 1][j]推出，即背包容量为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[i][j]的定义出发，如果背包容量j为0的话，即dp[i][0]，无论是选取哪些物品，背包价值总和一定为0
其次，i 是由 i-1 推导出来，那么i为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.确定遍历顺序
5.推导dp数组

代码

    public static void main(String[] args) {
    
        int[] weight = {
    1, 3, 4};
        int[] value = {
    15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
    
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
    
            for (int j = 1; j <= bagsize; j++){
    
                if (j < weight[i - 1]){
    
                    dp[i][j] = dp[i - 1][j];
                }else{
    
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
    
            for (int j = 0; j <= bagsize; j++){
    
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

一维数组

思路

使用二维数组的时候，递推公式：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[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2.一维dp数组的递推公式
dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[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[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值， dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3.初始化
dp[0]是0，因为背包容量为0所背的物品的最大价值就是0。
4.一维dp数组遍历顺序

  public static void main(String[] args) {
    
        int[] weight = {
    1, 3, 4};
        int[] value = {
    15, 20, 30};
        int bagWight = 4;
        testWeightBagProblem(weight, value, bagWight);
    }

    public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    
        int wLen = weight.length;
        //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
        int[] dp = new int[bagWeight + 1];
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 0; i < wLen; i++){
    
            for (int j = bagWeight; j >= weight[i]; j--){
    
                dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
        //打印dp数组
        for (int j = 0; j <= bagWeight; j++){
    
            System.out.print(dp[j] + " ");
        }
    }

416分割等和子集

题目

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例：

思路

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。

要注意题目描述中！！！商品是不是可以重复放入。
即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

本题中我们要使用的是01背包，因为元素我们只能用一次。

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

背包的体积为sum / 2
背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
背包如果正好装满，说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。
1.确定dp数组以及下标的含义
01背包中，dp[j] 表示： 容量为j的背包，所背的物品价值可以最大为dp[j]。套到本题，dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]。
2.确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

代码

class Solution {
    
    public boolean canPartition(int[] nums) {
    
        //dp[j]表示 背包总容量是j，最大可以凑成j的子集总和为dp[j]
        int sum = 0;
        for(int num : nums){
    
            sum += num;
        }
        if(nums.length == 1) return false;
        if(sum % 2 == 1)  return false;
        int target = sum / 2;
        int[] dp = new int[target+1];
        dp[0] = 0;        
        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]);
            }
        }
        return dp[target] == target;
    }
}

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

题目

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例：

思路

尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。
1.确定dp数组以及下标的含义
dp[j]表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背dp[j]这么重的石头。
2.确定递推公式
01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题则是：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
3.初始化
4.确定遍历顺序
5.结果
最后dp[target]里是容量为target的背包所能背的最大重量。
那么分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。
在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。
那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]

代码

class Solution {
    
    public int lastStoneWeightII(int[] stones) {
    
        int len = stones.length;
        int sum = 0;
        for(int num : stones){
    
            sum += num;
        }
        int target = sum / 2;
        int[] dp = new int[target+1];
        for(int i = 0; i < len; i++){
    
            for(int j = target; j >= stones[i]; j--){
    
                dp[j] = Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        return (sum-dp[target]) - dp[target];

    }
}

494. 目标和

题目

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例：

思路

加法的总和为x，那么减法对应的总和就是sum - x
sum为数组中元素之和。
+x - (sum - x) = target ----> x = (sum+target) /2;
此时问题就转化为，装满容量为x背包，有几种方法。

1.确定dp数组以及下标的含义
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
2. 确定递推公式
dp[j] += dp[j - nums[i]]
3.初始化
dp[0] = 1 装满容量为0的背包，有1种方法，就是装0件物品
4.确定遍历顺序

代码

class Solution {
    
    public int findTargetSumWays(int[] nums, int target) {
    
        //数组中每个数都有两个值，一个是正值，一个负值
        //dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
        int len = nums.length;
        int sum = 0;
        for(int num : nums){
    
            sum += num;
        }
        //加法的总和为x，那么减法对应的总和就是sum - x,sum为数组中元素之和。
        //+x - (sum - x) = target ----> x = (sum+target) /2;
        if((sum + target) % 2 == 1)  return 0;
        if(Math.abs(target) > sum)  return 0;
        int size = (sum + target) / 2;
        //！！！ 要考虑size < 0,否则java.lang.NegativeArraySizeException
        if(size < 0)  size = -size;
        int[] dp = new int[size+1];
        dp[0] = 1;
        for(int i = 0; i < len; i++){
    
            for(int j = size; j >= nums[i]; j--){
    
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];

    }
}

474. 一和零

题目

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例：

思路

strs 数组里的元素就是物品，每个物品都是一个。 m 和 n相当于是一个背包，两个维度的背包。
1.确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
2.确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
3.初始化
4.确定遍历顺序
外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历！

代码

class Solution {
    
    public int findMaxForm(String[] strs, int m, int n) {
    
        //dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
        int[][] dp = new int[m+1][n+1];
        for(String str : strs){
    
            int zeroNum = 0;
            int oneNum = 0;
            for(char c : str.toCharArray()){
    
                if(c == '0')  zeroNum++;
                else  oneNum++;
            }
            for(int i = m; i >= zeroNum; i--){
    
                for(int j = n; j >= oneNum; j--){
    
                    dp[i][j] = Math.max(dp[i][j],dp[i-zeroNum][j-oneNum] + 1);
                }
            }
        }
        return dp[m][n];

    }
}