UVa 11088

Summary

You're trying to make the most groups of threes as possible. Since $N\leq 15$ , this is a time for Dynamic Programming, as there are only $N^{3}$ subproblems.

Explanation

Using Dynamic Programming, we can solve the problem with its subproblem as such:

$best(S)=0{\mbox{ where }}|S|<3$ $best(S=\{a_{1},a_{2},a_{3},\ldots ,a_{n}\})=\max _{i,j,k}\left(best(S-a_{i}-a_{j}-a_{k})+{\begin{cases}1,&{\mbox{if }}a_{i}+a_{j}+a_{k}\geq 20\\0,&{\mbox{otherwise}}\end{cases}}\right)$ Basically, what this is saying is, if the current subproblem has less than 3 people, it can't form a team, so it will give the answer 0. Otherwise, take the max $i,j,k$ such that it yields the best results from the rest that weren't used. Since there are at most $O(2^{N})$ subproblems, saving the results down is good enough.

Optimizations

The naive implementation is $O(N^{3}2^{N})$ . There's an $O(N^{2}2^{N})$ solution which takes advantages of the fact that you should always include the "biggest" element in the set in the next step.

Input

9
22 20 9 10 19 30 2 4 16
2
15 3
0

Case 1: 3
Case 2: 0

Implementation

/*
Problem: 11088 - End up with More Teams
(http://blogaritmo.factorcomun.org)

Accepted
*/

#include <algorithm>
#include <iostream>
#include <cstdio>

using namespace std;

#define bit(i, n) (n & (1 << i))

int memo[1<<15], x, n;

/*
Returns the maximum amount of teams that can be made using
teams set on on bitwise mask avail. At each step, I try to
build a new team using the first available person, or igno-
re that person completely.
*/
int best(int avail){
int &ans = memo[avail];
if (ans == -1){
ans = 0;
for (int i=0; i<n; ++i)
if (bit(i, avail)){
ans = max(ans, best(avail & ~(1 << i))); //Ignore this dogg
for (int j=i+1; j<n; ++j)
if (bit(j, avail))
for (int k=j+1; k<n; ++k)
if (bit(k, avail))
if(x[i] + x[j] + x[k] >= 20)
ans = max(ans, 1 + best(avail & ~(1 << i) & ~(1 << j) & ~(1 << k))); //Make team (i, j, k).
break;
}
}
return ans;
}

int main(){
int pizza = 1;
while (scanf("%d", &n) == 1 && n){
for (int i = 0; i<n; ++i) scanf("%d", &x[i]);

memset(memo, -1, sizeof memo);
printf("Case %d: %d\n", pizza++, best((1 << n) - 1));
}

return 0;
}