Problem 1032 : Course Planning for Lazy Students

Problem D: Course Planning for Lazy Students
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1032

問題概要

ある教科をとるためには前の教科をとっていなければならない学校（うちの学校）での履修計画。
一定の単位数を満たすために最低限の単位数を求めなさい。

解法

全探索。
とるかとらないか,2^20でもとまる。

ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)

const int N = 20;

using namespace std;

class Course{
public:
  bool r[N], flag;
  int cost;
  bool ok(const bool *t){
    rep(i, N){
      if(r[i] && !t[i])return false;
    }
    return true;
  }
  Course(){
    flag = false;
    rep(i, N)r[i] = false;
  }
};
int n, u, ans;
void search(int now, int cost, bool *t, int num, vector<Course> &v){
  if(cost >= u){
    bool ok = true;
    FOR(it, v){
      if(!(*it).flag)continue;
      if((*it).ok(t))continue;
      ok = false; 
      break;
    }
    if(ok)ans = min(ans, num);
    return;
  }
  if(num >= ans)return;
  if(now >= n)return;
  search(now+1, cost, t, num , v);
  t[now] = true;
  cost += v[now].cost;
  v[now].flag = true;
  search(now+1, cost, t, num+1, v);
  t[now] = false;
  v[now].flag = false;
  cost -= v[now].cost;
  return;
}

main(){
  while(cin >> n >> u){
    if( n + u == 0)break;
    ans = 100000;
    vector<Course> v(N);
    rep(i, n){
      cin >> v[i].cost;
      int num;
      cin >> num;
      rep(j, num){
	int tmp;
	cin >> tmp;
	v[i].r[tmp] = true;
      }
    }
    bool t[N];
    rep(i, N)t[i] = false;
    search(0, 0, t, 0, v);
    cout << ans << endl;
  }
}