This is a special case of Max-SAT, where each clause can only contain variables which are close together (in a circular order). Specifically:

• Each animal is a boolean variable in Max-SAT. We have ~N~ variables ~X_1, \dots, X_N~ in a circular order.
• Each child is a clause in Max-SAT. If a child can see ~k~ consecutive enclosures, this means that each clause may only contain variables ~X_c, X_{c+1}, \dots, X_{c+k-1}~ for some ~c~ (where ~X_{N+1} = X_1~, ~X_{N+2} = X_2~ and so on). For this problem, we are given ~k = 5~.

A model solution uses dynamic programming.

Linear case

Consider a simpler problem when the enclosures ~X_1, \dots, X_N~ are placed in a linear order (i.e., ~X_N~ does not wrap back around to ~X_1~). For each ~i~, let ~\mathcal C_i~ be the set of all children whose visible enclosures lie in the range ~X_1, \dots, X_i~. We iterate through ~i = 1, 2, \dots, N~, and at each stage we solve problems of the following form:

Consider the set of children ~\mathcal C_i~, and consider all ~2^k~ ways in which the final ~k~ enclosures ~X_{i-k+1}, X_{i-k+2}, \dots, X_i~ may be filled or empty. For each filled/empty combination for enclosures ~X_{i-k+1}, X_{i-k+2}, \dots, X_i~, what is the maximum number of children in ~\mathcal C_i~ who can be made happy?

We solve the problems at stage ~i~ as follows. We assume we have already computed the maximum number of happy children in ~\mathcal C_{i-1}~ for all filled/empty combinations for enclosures ~X_{i-k}, \dots, X_{i-1}~. To calculate the new answers for stage ~i~ and a particular filled/empty combination for enclosures ~X_{i-k+1}, X_{i-k+2}, \dots, X_i~:

1. We count how many "new" children in ~\mathcal C_i-\mathcal C_{i-1}~ are made happy. We can calculate this directly from our choice of filled/empty values for ~X_{i-k+1}, X_{i-k+2}, \dots, X_i~, because every "new" child is looking at precisely these enclosures.
2. Assuming the "old" enclosure ~X_{i-k}~ is filled, we can look up our solutions from stage ~i-1~ to find out how many children in ~\mathcal C_{i-1}~ can be made happy with our selected filled/empty values for ~X_{i-k+1}, \dots, X_{i-1}~. Likewise, we can look up how many children in ~\mathcal C_{i-1}~ can be made happy when the old enclosure ~X_{i-k}~ is empty. The larger of these two numbers tells us how many "old" children in ~\mathcal C_{i-1}~ we can keep happy overall.
3. The number of happy "new" children from step 1 can be added to the number of happy "old" children from step 2, giving the solution to our current problem.

The total number of problems to solve is ~2^k N~, and the overall running time for the algorithm is ~\mathcal O(2^k (N+C))~. The space required is only ~\mathcal O(2^k)~, since each stage ~i~ only requires the solutions from the previous stage ~i-1~.

Circular case

In the circular case, we need to permanently remember the states of the first ~k-1~ enclosures ~X_1, \dots, X_{k-1}~ (in addition to the "most recent" ~k~ enclosures ~X_{i-k+1}, \dots, X_i~). This allows us to correctly deal with the final children who can see back around past ~X_N~ to ~X_1, \dots, X_{k-1}~ again. The remainder of the algorithm remains more or less the same.

We therefore have ~2^{2k}~ problems to solve at each stage, giving running time ~\mathcal O(2^{2k} (N+C))~ and storage space ~\mathcal O(2^{2k})~.