【算法系列之动态规划III】背包问题

背包问题

1. 01背包指的是物品只有1个，可以选也可以不选。
2. 完全背包是物品有无数个，可以选几个也可以不选。

二维数组01背包

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

输入: 
weight: [1,3,4],value: [15,20,30],背包体积: 4
输出：35

解题思路

1. dp数组，从下标[0-i]的物品里面任意取，放进容量为j的背包，价值总和最大是多少。
2. 不放物品i，物品i由于体积问题放不进去，dp[i][j]=dp[i-1][j]
3. 放物品i，dp[i][j]=dp[i-1][j-weight[i]]+value[i]

Java实现

public class BagProblem {public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagSize = 4;System.out.println(new BagProblem().testWeightBagProblem(weight, value, bagSize));}public int testWeightBagProblem(int[] weight, int[] value, int bagSize) {int size = weight.length;//0-size-1个物品放入到大小为bagSize的背包中int[][] dp = new int[size][bagSize + 1];//当bagSize=0时，dp[i][0]=0//当只有索引为0的物品可以选择，且放的下(j<=bagSize)，dp[0][j]的值等于放入索引为0的价值for (int j = weight[0]; j <= bagSize; j++) {dp[0][j] = value[0];}for (int i = 1; i < size; i++) {for (int j = 1; j <= bagSize; j++) {if (j < weight[i]) {/*** 当前背包的容量都没有当前物品i大的时候，是不放物品i的* 那么前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]] + value[i]);}}}for (int i = 0; i < size; i++) {for (int j = 0; j <= bagSize; j++) {System.out.print(dp[i][j] + "\t");}System.out.println("\n");}return dp[size - 1][bagSize];}
}

一维数组01背包

解题思路

1. dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。
2. 递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
3. 遍历详解：当i=0，初始化dp[j]，只有j>weight[i]的时候，会被初始化。当i=1的时候，可以选择的商品有[0,1]，dp[j]是在原有的dp数组上判断的，只有当可以存放下索引为1的商品，且dp[j - weight[i]] + value[i]>dp[j]，该数值才会被更新。
4. 选择逆序背包容量，主要是dp[j]和dp[j-weight[i]]的初始化顺序的问题。在二维数组中，比较的是dp[i-1][j-weight[i]]，是第i-1层的dp[j-weight[i]]

Java实现

public class BagProblem_II {public static void main(String[] args) {int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWight = 4;System.out.println(new BagProblem_II().testWeightBagProblem(weight, value, bagWight));}private int 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]);System.out.println(dp[j] + "," + j + "," + i);}}//打印dp数组for (int j = 0; j <= bagWeight; j++) {System.out.print(dp[j] + " ");}System.out.println();return dp[bagWeight];}
}

416. 分割等和子集

力扣题目链接

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

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

解题思路

1. 集合里能否出现总和为 sum / 2 的子集
2. dp[j]：最大值为j的子集
3. 如果第i个元素没有放到集合中，值是dp[i-1][j]；如果第i个元素放进集合中，值是dp[i-1][j-num[i]]+num[i]。

dp[i][j]= dp[i−1][j]，当i-1的数组已经满足了等于j的条件
dp[i][j]= true, 当nums[i] = j满足。
dp[i−1][j−nums[i]].当nums[i] < j。
dp[i][j]为true的三个条件，只需要满足一个即可。

Java实现

    public boolean canPartition(int[] nums) {if (nums == null || nums.length == 0) return false;int len = nums.length;int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];}if (sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < len; 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。

输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

解题思路

1. dp[target]里是容量为target的背包所能背的最大重量。分成两堆石头，一堆石头的总重量是dp[target]，另一堆就是sum - dp[target]。相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]。

Java实现

class Solution_LC1049 {public int lastStoneWeightII(int[] stones) {int sum = 0;for (int i : stones) {sum += i;}int target = sum >> 1;//初始化dp数组int[] dp = new int[target + 1];for (int i = 0; i < stones.length; i++) {//采用倒序for (int j = target; j >= stones[i]; j--) {//两种情况，要么放，要么不放dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);}}return sum - 2 * dp[target];}
}

494.目标和

力扣题目链接

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

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

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

解题思路

1. 数组集合可以分为正数集合和负数集合，正+负=sum，正-负=target，题目可以转化为求sum=正数的子集合的个数。
2. 纯01背包问题：装满背包最大的价值是多少；分割等和子集，能不能装满这个背包；最后一块石头的重量，给定背包，能装多少装多少；目标和：装满这个背包有多少方法？
3. dp数组的含义：填满j（包括j）这么大容积的包，有dp[j]种方法。
4. dp[j]=dp[j-nums[i]]的累加。比如nums[i]=2，dp[5]+=dp[5-nums[i]]。

Java实现

class Solution_LC494 {public int findTargetSumWays(int[] nums, int target) {int len = nums.length;int sum = 0;for (int i = 0; i < len; i++) {sum += nums[i];}if (target > sum || target < -sum) {return 0;}if ((target + sum) % 2 != 0) {return 0;}int goal = (target + sum) / 2;//填满j（包括j）这么大容积的包，有dp[j]种方法int[] dp = new int[goal + 1];dp[0] = 1;for (int i = 0; i < nums.length; i++) {for (int j = goal; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[goal];}
}

二维数组的实现

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}int diff = sum - target;if (diff < 0 || diff % 2 != 0) {return 0;}int n = nums.length, neg = diff / 2;int[][] dp = new int[n + 1][neg + 1];dp[0][0] = 1;for (int i = 1; i <= n; i++) {int num = nums[i - 1];for (int j = 0; j <= neg; j++) {dp[i][j] = dp[i - 1][j];if (j >= num) {dp[i][j] += dp[i - 1][j - num];}}}return dp[n][neg];}
}

474.一和零

力扣题目链接

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

解题思路

1. dp[i][j]表示i个0和j个1时的最大子集

Java实现

class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp = new int[m + 1][n + 1];for (String str : strs) {int zeroNum = 0;int oneNum = 0;for (int i = 0; i < str.length(); i++) {if (str.charAt(i) == '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];}
}

总结一下

纯 0 - 1 背包 是求 给定背包容量 装满背包 的最大价值是多少。
416. 分割等和子集 是求 给定背包容量，能不能装满这个背包。
1049. 最后一块石头的重量 II 是求 给定背包容量，尽可能装，最多能装多少
494. 目标和 是求 给定背包容量，装满背包有多少种方法。
本题是求 给定背包容量，装满背包最多有多少个物品。