474. Ones and Zeroes

Problem

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 m0s 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".

Problem Summary

In the computer world, we always pursue gaining the maximum benefit with limited resources. Now, suppose you control m 0s and n 1s respectively. In addition, there is an array of strings containing only 0s and 1s. Your task is to use the given m 0s and n 1s to find the maximum number of strings from the array that can be formed. 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 length of the given string array will not exceed 600.

Solution Approach

• Given a string array and m, n, where all characters consist of 0 and 1. Determine the maximum number of strings that can be taken from the array such that the total number of 0s in the selected strings is ≤ m and the total number of 1s is ≤ n.
• This problem is a typical 0-1 knapsack problem. It is just a two-dimensional knapsack problem. Select certain items from n items to fill as much as possible the knapsack in the m dimension and the n dimension. Why fill as much as possible? Because the knapsack may not be completely filled.
• dp[i][j] represents the total number of items that can be put into a knapsack with capacity (i,j) while filling it as much as possible. The state transition equation is dp[i][j] = max(dp[i][j], 1+dp[i-zero][j-one]). Here, zero represents the volume of the current item in the m dimension, that is, the number of 0s. one represents the volume of the current item in the n dimension, that is, the number of 1s. Each time an item is added, compare the total number of items in the current (i,j) knapsack with the total number of items in the (i-zero,j-one) knapsack + 1, compare the two values, and save the maximum of them. Refresh this two-dimensional knapsack each time an item is added, until all items have been scanned once. The final answer is stored in dp[m][n]. The time complexity is O( n * M * N ).

Code

package leetcode

import "strings"

func findMaxForm(strs []string, m int, n int) int {
	dp := make([][]int, m+1)
	for i := 0; i < m+1; i++ {
		dp[i] = make([]int, n+1)
	}
	for _, s := range strs {
		zero := strings.Count(s, "0")
		one := len(s) - zero
		if zero > m || one > n {
			continue
		}
		for i := m; i >= zero; i-- {
			for j := n; j >= one; j-- {
				dp[i][j] = max(dp[i][j], 1+dp[i-zero][j-one])
			}
		}
	}
	return dp[m][n]
}