江苏建设外贸公司网站,做微信号公众号用网站还是App,做外汇看什么网站,网络设计规划师文章目录前言一、一和零#xff08;力扣474#xff09;二、完全背包前言
1、一和零 2、完全背包理论基础 一、一和零#xff08;力扣474#xff09;
求装满这个背包最多有多少个物品 给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集…
文章目录前言一、一和零力扣474二、完全背包前言
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个0oneNum个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 3n 3为例 最后dp数组的状态如下所示
class Solution {public int findMaxForm(String[] strs, int m, int n) {int[][] dp new int[m1][n1];int oneNum;int zeroNum;for(int x 0; xstrs.length; x){oneNum 0;zeroNum 0;for(char ch : strs[x].toCharArray()){if( ch 0){zeroNum;}else oneNum;}for(int im;izeroNum;i--){for(int jn;joneNum;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 );}
}
