问个google面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问个google面试题

问个google面试题# JobHunting - 待字闺中

B*12011-10-19 07:10

1 楼

Given an array of strings of 0s and 1s. X and Y are also given. Return the
maximum number of elements in a subset of the array elements which will X
number of zeroes and Y number of 1s when combined. For eg: if array[] = {"01
", "10", "0", "110"} X=3, Y=2
Answer should be 3 since first 3 strings when combined will give the
required number of 0s and 1s.
这题是不是要用dp啊。

s*j2011-10-19 07:10

2 楼

就是二维背包问题吧
f[i][j]表示i个0，j个1的时候，最多用到几个元素，然后顺着推就可以了

01

【在 B*******1 的大作中提到】

: Given an array of strings of 0s and 1s. X and Y are also given. Return the
: maximum number of elements in a subset of the array elements which will X
: number of zeroes and Y number of 1s when combined. For eg: if array[] = {"01
: ", "10", "0", "110"} X=3, Y=2
: Answer should be 3 since first 3 strings when combined will give the
: required number of 0s and 1s.
: 这题是不是要用dp啊。