问题 E: 二进制字符串背包问题
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:10
解决:6
题目描述
小明正在学习动态规划算法,他遇到了一个有趣的背包问题。给定一个由二进制字符串组成的数组和两个整数m、n,需要找出最大子集的长度,使得该子集中最多包含m个'0'和n个'1'。
这个问题可以看作是一个二维费用的01背包问题,每个字符串都有两个"重量":包含的'0'的数量和'1'的数量,而我们的"背包容量"分别是m和n。
输入
第一行: 三个整数 k、m、n
k:二进制字符串的数量 (1 ≤ k ≤ 600)
m:最多可以包含的'0'的数量 (1 ≤ m ≤ 100)
n:最多可以包含的'1'的数量 (1 ≤ n ≤ 100)
接下来k行: 每行一个二进制字符串
每个字符串长度不超过100
字符串仅由'0'和'1'组成
输出
输出一个整数,表示满足条件的最大子集的长度。
样例输入 复制
5 5 3
10
0001
111001
1
0
样例输出 复制
4
提示
1 ≤ k ≤ 600
1 ≤ 每个字符串长度 ≤ 100
1 ≤ m, n ≤ 100
字符串仅包含'0'和'1'