【动态规划】【01背包 给定背包容量，装满背包最多有多少个物品】Leetcode 474. 一和零

本文主要是介绍【动态规划】【01背包 给定背包容量，装满背包最多有多少个物品】Leetcode 474. 一和零，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---------------🎈🎈474. 一和零 题目链接🎈🎈-------------------

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

解法

😒: 我的代码实现============>

动规五部曲
相当于是一个背包——这里背包有两个维度：m个0，n个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[m+1][n+1];// 【遍历顺序】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; a>=x ; a--){ // 【倒序遍历这个二维背包,这里的顺序无所谓】for(int b = n; b>=y ; 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];}
}          

这篇关于【动态规划】【01背包 给定背包容量，装满背包最多有多少个物品】Leetcode 474. 一和零的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---