day43【代码随想录】动态规划之一和零、完全背包理论基础

---

前言

1、一和零
2、完全背包理论基础

---

一、一和零（力扣474）

求装满这个背包最多有多少个物品
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

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

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

背包容量是二维的 m个0 n个1 限制
思路：
动规五部曲
1、确定dp[]数组以及下标含义
dp[i][j]：i个0 j个1 最多装了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);

对比下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

3、dp数组如何初始化

01背包的dp数组初始化为0就可以。
4、确定遍历顺序
外层for循环遍历物品，内层for循环遍历背包容量且从后向前遍历

5、举例推导dp数组
以输入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3为例
最后dp数组的状态如下所示：

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

二、完全背包

完全背包和01背包的区别所在： 物品在完全背包中可以使用无数次。

而在01背包一维dp数组中，倒序遍历背包容量就是为了保证每个物品只取一次，那么如何能让这个物品无限次使用呢？改为正序遍历

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

遍历顺序：
两层for循环可以相互颠倒
遍历物品在外层循环，遍历背包容量在内层循环（按行），状态如图：

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

遍历背包容量在外层循环，遍历物品在内层循环（按列），状态如图：

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

完整代码：

//先遍历物品，再遍历背包
private static void testCompletePack(){int[] weight = {1, 3, 4};int[] value = {15, 20, 30};int bagWeight = 4;int[] dp = new int[bagWeight + 1];for (int i = 0; i < weight.length; i++){ // 遍历物品for (int j = weight[i]; j <= bagWeight; j++){ // 遍历背包容量dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}for (int maxValue : dp){System.out.println(maxValue + "   ");}
}

---