I've thought about it for days and I'm getting no where. And I've searched online about similar problems but also no luck. So I'm seeking help here. I would really appreciate it if you can give me any hint or info.
Here's the problem:
Given N bins, each bin has M_1, M_2, ... M_N balls. Each bin holds balls with the same color. And any 2 different bins hold balls with different colors.
Given P, 1 <= P <= N, each time, we want to draw P balls with different colors from the N bins. So that simply means we draw 0 or 1 balls from each bin.
What I want is the max number of times, MAX, that I can do such draws from the N bins.
I've already proved that the way to get MAX is to draw the bins holding the max number of balls each time.
For example:
given N=6 bins, each has 2, 2, 2, 3, 5, 7 balls, and let P=4, the process to get the maximum is:
2, 2, 2, 3, 5, 7 1, 2, 2, 2, 4, 6 1, 1, 1, 2, 3, 5 0, 1, 1, 1, 2, 4 0, 0, 0, 1, 1, 3
So we get MAX=4 times.
However the problem is I'm not able to figure out a closed form for MAX. And I'm also not able to figure out an algorithm that is a reasonably well polynomial of N, such as O(N), O(NlogN) (yet it's not a polynomial, but is still good), or O(N^2).
Thanks for any hints or tips.