> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/knapsack-problem/474-ones-and-zeroes.md).

# 474     Ones and Zeroes

## 474. [Ones and Zeroes](https://leetcode.com/problems/ones-and-zeroes/description/)

## 1. Question

In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.

For now, suppose you are a dominator of **m**`0s`and **n**`1s`respectively. On the other hand, there is an array with strings consisting of only`0s`and`1s`.

Now your task is to find the maximum number of strings that you can form with given**m**`0s`and**n**`1s`. Each`0`and`1`can be used at most **once**.

**Note:**

1. The given numbers of`0s`and`1s`will both not exceed`100`
2. The size of given string array won't exceed`600`.

**Example 1:**

```
Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3

Output: 4

Explanation:
This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”
```

**Example 2:**

```
Input: Array = {"10", "0", "1"}, m = 1, n = 1

Output: 2


Explanation:
You could form "10", but then you'd have nothing left. Better form "0" and "1".
```

## 2. Implementation

**(1) DP**

思路: 这题要我们用m个0和n个1，组成最多的string(每个string都由0或1组成)。这是很明显的0-1背包问题，是二维的0-1背包问题，可以直接用模板写

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0 || m < 0 || n < 0) {
            return 0;
        }

        // dp[i][j][k] means the max number of strings we can form with number of j 0s and k 1s for the first i strings in strs
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i <= strs.length; i++) {
            // The first row is empty string, skip the first row
            if (i == 0) continue;

            count = countOnesAndZeroes(strs[i - 1]);

            for (int j = 0; j <= m; j++) {
                for (int k = 0; k <= n; k++) {
                    // When we have enough 1s and 0s to form the current string string strs[i - 1]
                    // Two strategies: Form it or skip it
                    if (count[0] <= j && count[1] <= k) {
                        dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count[0]][k - count[1]] + 1);
                    }
                    // Do nothing
                    else {
                        dp[i][j][k] = dp[i - 1][j][k];
                    }
                }
            }
        }
        return dp[strs.length][m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c : s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}
```

**(2) DP空间优化**

```java
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        if (strs == null || strs.length == 0|| m < 0 || n < 0) {
            return 0;
        }

        int[][] dp = new int[m + 1][n + 1];
        int[] count = new int[2];

        for (int i = 0; i < strs.length; i++) {
            count = countOnesAndZeroes(strs[i]);

            for (int j = m; j >= count[0]; j--) {
                for (int k = n; k >= count[1]; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - count[0]][k - count[1]] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int[] countOnesAndZeroes(String s) {
        int[] count = new int[2];

        for (char c :s.toCharArray()) {
            ++count[c - '0'];
        }
        return count;
    }
}
```

## 3. Time & Space Complexity

**DP:** 时间复杂度O(k \* l \* m \* n), 空间复杂度O(kmn)

**DP空间优化:** 时间复杂度O(k \* l \* m \* n), 空间复杂度O(mn)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://protegejj.gitbook.io/algorithm-practice/leetcode/dynamic-programming/knapsack-problem/474-ones-and-zeroes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.