TheAlgorithms / Ruby

All algorithms implemented in Ruby
MIT License
1.15k stars 289 forks source link

Ones and Zeros: Dynamic Programming approach #177

Closed vbrazo closed 2 years ago

vbrazo commented 3 years ago

You are given an array of binary strings strs and two integers m and n. Return the size of the largest subset of strs such that there are at most m 0's and n 1's in the subset. A set x is a subset of a set y if all elements of x are also elements of y.

strs = %w[10 0001 111001 1 0]
m = 5
n = 3
puts find_max_form(strs, m, n)
# Output: 4

strs = %w[10 0 1]
m = 1
n = 1
puts find_max_form(strs, m, n)
# Output: 2