leetcode 474. Ones and zeroes (medium)

One 、 The main idea of the topic

label :  Dynamic programming

https://leetcode.cn/problems/ones-and-zeroes

Here's an array of binary strings  strs  And two integers  m  and  n .

Please find out and return to  strs  Length of the largest subset of , This subset   most   Yes  m  individual  0  and  n  individual  1 .

If  x  All of the elements of are also  y  The elements of , aggregate  x  Is a collection  y  Of   A subset of  .

Example  1：

Input ：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3

Output ：4

explain ： At most  5  individual  0  and  3  individual  1  The largest subset of is  {"10","0001","1","0"} , So the answer is  4 . Other smaller subsets that satisfy the question include  {"0001","1"}  and  {"10","1","0"} .{"111001"}  Not satisfied with the question , Because it contains  4  individual  1 , Greater than  n  Value  3 .

Example  2：

Input ：strs = ["10", "0", "1"], m = 1, n = 1

Output ：2

explain ： The largest subset is  {"0", "1"} , So the answer is  2 .

Tips ：

• 1 <= strs.length <= 600

• 1 <= strs[i].length <= 100

• strs[i]&nbsp; Only by &nbsp;'0'  and &nbsp;'1'  form

• 1 <= m, n <= 100

Two 、 Their thinking

This problem is also a knapsack problem , knapsack problem ： Yes N Items and capacity are W The backpack , Each item has its own volume w And value v, Find out which items can make the total value of the items contained in the backpack the greatest . If you limit each item to 0 Or 1 individual , The problem is called 0-1 knapsack problem ; If you don't limit the number of items , Then the problem is called unbounded knapsack problem or complete knapsack problem .

We can use dynamic programming to solve the knapsack problem . With 0-1 Take the backpack problem for example . We can define a two-dimensional array dp Store maximum value , among dp[i][j] Before presentation i The volume of each article shall not exceed j The maximum value that can be achieved in the case of . Before we traverse to the i When it comes to items , At present, the total capacity of the backpack is j Under the circumstances , If we don't put things i Put it in the backpack , that dp[i][j]=dp[i-1][j], The former i The maximum value of an item is equal to taking only the first i-1 The maximum value of an item ; If we put things i Put it in the backpack , Hypothesis number 1 i The volume of this item is w, Value is v, So we get dp[i][j]=dp[i-1][j-w] + v. We can take the maximum value of these two cases in the traversal process , The total time complexity and space complexity are O(NW).

3、 ... and 、 How to solve the problem

3.1 Java Realization

public class Solution {
 public int findMaxForm(String[] strs, int m, int n) {
 int[][] dp = new int[m + 1][n + 1];
 for (String str : strs) {
 int[] countArr = count(str);
 int count0 = countArr[0];
 int count1 = countArr[1];
 for (int i = m; i>= count0; i--) {
 for (int j = n; j>= count1; j--) {
 dp[i][j] = Math.max(dp[i][j], 1 + dp[i-count0][j-count1]);
 }
 }
 }
 return dp[m][n];
 }

 /**
 *  In the calculation string 0 and 1 The number of
 */
 int[] count(String s) {
 int count0 = s.length();
 int count1 = 0;
 for (char c : s.toCharArray()) {
 if ('1' == c) {
 count1++;
 count0--;
 }
 }
 return new int[]{count0, count1};
 }
}


Four 、 Summary notes

• 2022/6/30 7.5 It will be extended for another week or so