Maximum children happiness

Question

Given N different candies and M children. Each of the children demands for K[i] different candies and will only be happy iff he get all those different candies which he demanded.

Now I want to maximize the number children that get happy. How should I distribute the candies?

Example: Let's have N=4 candies and M=3 children:

1st child requires 2 (K[1]) candies which are: 1 and 2
2nd child requires 2 (K[2]) candies which are: 2 and 3
3rd child requires 2 (K[3]) candies which are: 3 and 4

The answer here is 2 as I can at best only make the 1st and 3rd child happy.

My attempt:

Give candies to children in the order of the amounts that they require to be happy (i.e. K[i]). In other words, you should only give candy to a child if you have made happy all the children that demand less, and every time you give candy to one of them you have to give them the whole amount that they require.

Is this solution correct?

What would your solution do when two children ask for the same number of candies? If you choose randomly, your algorithm fails for your own example. — Shahbaz, Mar 11 '14 at 11:05
Exact copy of http://stackoverflow.com/questions/22302459/selecting-maximum-number-of-choice — Ivaylo Strandjev, Mar 11 '14 at 11:05
Reframed question from ongoig programming contest(Codechef March 2014). — Vikram Bhat, Mar 11 '14 at 11:19

score 1 · Answer 1 · answered Mar 11 '14 at 11:05

1

Yes, you are wrong. Consider:

Wants candies 1, 2, 3, and 4.
Wants candies 1, 5, 6, 7, 8, and 9.
Wants candies 2, 10, 11, 12, 13, 14, and 15.
Wants candies 3, 16, 17, 18, 19, 20, and 21.
Wants candies 4, 22, 23, 24, 25, 26, and 27.

Your algorithm will only make child 1 happy. But you can make 2, 3, 4, and 5 happy.

answered Mar 11 '14 at 11:05

David Schwartz

179,497
17
214
278

oh right..so could you please provide correct algorithm for it ? – user3405426 Mar 11 '14 at 11:06
The simplest one -- try every possible combination. – David Schwartz Mar 11 '14 at 11:14
@DavidSchwartz http://tinyurl.com/o8fypwj – BlackBear Mar 11 '14 at 11:24

Vikram Bhat · Answer 2 · 2014-03-11T11:31:29.103

As this a problem in on-going programming contest i cannot give you much of an answer but will push you in right direction. The problem you are solving is np complete as it can be reduced to maximum independent set and hence it can only be solved in general case using brute force which is trying out all combinations. You can reduce computations by checking if new set added is not intersecting with the other in this way you can skip a lot of invalid combinations.

Maximum children happiness

2 Answers2