别人不能注册我的wordpress站,thinkphp 网站模版,深圳网站设计 制作,元氏网站制作【动态规划】【01背包 给定背包容量#xff0c;装满背包最多有多少个物品】Leetcode 474. 一和零 解法 ---------------#x1f388;#x1f388;474. 一和零 题目链接#x1f388;#x1f388;-------------------
纯 0 - 1 背包 是求 给定背包容量 装满背包 的最大价值… 【动态规划】【01背包 给定背包容量装满背包最多有多少个物品】Leetcode 474. 一和零 解法 ---------------474. 一和零 题目链接-------------------
纯 0 - 1 背包 是求 给定背包容量 装满背包 的最大价值是多少。 416. 分割等和子集是求 给定背包容量能不能装满这个背包。 1049. 最后一块石头的重量 II是求 给定背包容量尽可能装最多能装多少 494. 目标和是求 给定背包容量装满背包有多少种方法。 本题是求 给定背包容量装满背包最多有多少个物品。
解法
: 我的代码实现
动规五部曲 相当于是一个背包——这里背包有两个维度m个0n个1不同长度的字符串就是不同大小的待装物品。问尽量装满这个背包里面能装最多多少物品
✒️确定dp数组以及下标的含义 dp[i][j]容量为i个0和j个1的背包能装下的子集最多个数为dp[i][j]。 ✒️确定递推公式 dp[a][b] Math.max( 表示不放当前物品dp[a][b], 表示添加当前物品dp[a-x][b-y]1 ) ✒️dp数组初始化 初始为0 ✒️确定遍历顺序 01背包一定是外层for循环遍历物品内层for循环遍历背包容量且从后向前遍历 时间复杂度O(N) 空间复杂度O(N)
代码
class Solution {public int findMaxForm(String[] strs, int m, int n) {//0-1背包问题相当于是m个0和n个1大小的背包能装下多少元素// 【dp数组初始化】dp[a][b] : a个0 b个1 大小的背包能装下的最大子集个数 最终返回dp[m][n]即可 初始化全为0即可int[][] dp new int[m1][n1];// 【遍历顺序】0-1背包问题 一个物品只能取一次外层正向遍历物品内层倒序遍历背包for(int i 0; i strs.length; i){// 【遍历物品】得到每个物品的x,y————0的个数1的个数String str strs[i];int x 0; // 当前物品的0的个数int y 0; // 当前物品的1的个数for(int p 0; p str.length(); p){if(str.charAt(p) 0){x;}if(str.charAt(p) 1){y;}}for(int a m; ax ; a--){ // 【倒序遍历这个二维背包,这里的顺序无所谓】for(int b n; by ; b--){//【递推公式】dp[a][b] Math.max( 表示不放当前物品dp[a][b], 表示添加当前物品dp[a-x][b-y]1 )dp[a][b] Math.max(dp[a][b], dp[a-x][b-y]1);}}}return dp[m][n];}
}
