USACO 2.1 Healthy Holsteins

Brutal force approach using bit set to speed up search.

#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

int V, vit[26], G, feedType[16][26], vc;
bitset<16> minbit(0);

int main() {
  ifstream fin("holstein.in");
  ofstream fout("holstein.out");

  vc = 16;
	fin >> V;
	for(int i = 0; i < V; ++i)
		fin >> vit[i];

  fin >> G;
	for(int i = 0; i < G; ++i)
    for(int j=0 ; j < V; ++j)
      fin >> feedType[i][j];

  auto limit = 1 << G;
	for(int i = 0; i < limit; ++i) {
    int v[26] = {0};
		bitset<16> bit(i);
		for(int b = 0; b != G; ++b) {
      if(bit[b]) {
        for(int j = 0; j != V; ++j)
          v[j] += feedType[b][j];
      }
    }

		bool satisfy = true;
		for(int j = 0; j < V; ++j) {
      if(v[j] < vit[j]) {
        satisfy = false;
        break;
      }
    }

		if(satisfy && int(bit.count()) < vc && bit.to_ulong() > minbit.to_ulong()) {
			vc = static_cast<int>(bit.count());
			minbit = bit;
		}
	}

	fout << vc;
	for(int i = 0; i < G; ++i) {
    if(minbit[i])
      fout << " " << i + 1;
  }

	fout << endl;

  return 0;
}