UVa 11088

From Algorithmist
Jump to navigation Jump to search

11088 - End up with More Teams[edit]

Summary[edit]

You're trying to make the most groups of threes as possible. Since , this is a time for Dynamic Programming, as there are only subproblems.

Explanation[edit]

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

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 such that it yields the best results from the rest that weren't used. Since there are at most subproblems, saving the results down is good enough.

Optimizations[edit]

The naive implementation is . There's an solution which takes advantages of the fact that you should always include the "biggest" element in the set in the next step.

Input[edit]

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

Output[edit]

Case 1: 3
Case 2: 0

Implementation[edit]

/*
  Problem: 11088 - End up with More Teams
  Author: Andrés Mejía-Posada 
  (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[15], 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;
}