B*******1
发帖数: 2454 | 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****j
发帖数: 67 | 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啊。
| g**********y
发帖数: 14569 | 3 对，只要背包了，面试里可解的，最好的多半是DP。
【在 s****j 的大作中提到】
: 就是二维背包问题吧
: f[i][j]表示i个0，j个1的时候，最多用到几个元素，然后顺着推就可以了
:
: 01
| b*****c
发帖数: 1103 | 4 f[i][j][k]表示i个0，j个1的时候，前k个元素 最多用到几个元素
当然f[i][j][k]只跟f[i][j][k-1]相关 | B*******1
发帖数: 2454 | 5 Thanks.
【在 g**********y 的大作中提到】
: 对，只要背包了，面试里可解的，最好的多半是DP。
| c***7
发帖数: 315 | 6 这个怎么推啊
f[i][j]又不是f[i-1][j]能确定的
【在 s****j 的大作中提到】
: 就是二维背包问题吧
: f[i][j]表示i个0，j个1的时候，最多用到几个元素，然后顺着推就可以了
:
: 01
| s******n
发帖数: 3946 | 7 DP公式为
f[i,j,n] = max(f[i,j,n-1], f[i-zeros(n), j-ones(n), n-1] + 1) |
|
