schedule.java

import java.util.*;
public class schedule{
	public static ArrayList<Integer> sol;
	public static int max_weight=0;
	public static int max_cost=0;
	public static void main(String[] args){
		//ALL these is just to read data from standard input.
		Scanner in = new Scanner(System.in);
		//first line contains 1 integer, indicate how many courses specified by the user
		int n = in.nextInt();
		in.nextLine();
		sol = new ArrayList<Integer>();
		course[] courses = new course[n];
		for(int i=0;i<n;i++){
			//For each line
			Scanner st = new Scanner(in.nextLine());
			//The first string(no space allowed) is the name
			String name = st.next();
			//the second string is a integer, indicate the cost
			int cost = st.nextInt();
			//the 3rd string is a integer, intdicate the weight
			int weight = st.nextInt();
			//The rest are indices of which courses conflict with this one
			//index start from 0, so the nth line of the input
			//has index n-2.
			ArrayList<Integer> tmp = new ArrayList<Integer>();
			while(st.hasNextInt()){
				tmp.add(st.nextInt());
			}
			int[] r = new int[tmp.size()];
			for(int j=0;j<tmp.size();j++){
				r[j] = tmp.get(j);
			}
			course c = new course(name,weight,cost,r);
			courses[i] = c;
		}
		//This recursive function computes the result
		//the second parameter is the maximum cost allowed(if it's 24, then the solution
		//can be from 0 to 23
		b(courses, 24, n-1, new ArrayList<Integer>(), new boolean[n], 0);
		//output the weight, cost and the classes
		System.out.println(max_weight);
		System.out.println(max_cost);
		for(int i=0;i<sol.size();i++){
			System.out.println(courses[sol.get(i)].name);
		}
	}
	public static void b(course[] a, int limit, int c, ArrayList<Integer> s, boolean[] f, int w){
		//end condition
		if(c==-1||limit==0){
			return;
		}
		//if the current weight is better than the previous solution
		//make this the new solution
		if(w>max_weight){
			sol = new ArrayList<Integer>(s);
			max_weight = w;
			max_cost = 0;
			for(int i=0;i<sol.size();i++){
				max_cost += a[sol.get(i)].cost;
			}
		}
		//if the current wieght is the same
		//add this only if the cost is higher than the previous solution
		if(w==max_weight){
			int now_cost = 0;
			for(int i=0;i<s.size();i++){
				now_cost += a[s.get(i)].cost;
			}
			if(now_cost>max_cost){
				sol = new ArrayList<Integer>(s);
				max_cost = now_cost;
			}
		}
		//pick the item c if there is no conflict, and pass it on to the
		//next recursion
		if(f[c]==false&&a[c].cost<=limit){
			int[] t = a[c].constraint;
			ArrayList<Integer> diff = new ArrayList<Integer>();
			for(int i=0;i<t.length;i++){
				if(!f[t[i]]){
					diff.add(t[i]);
					f[t[i]]=true;
				}
			}
			s.add(c);
			b(a, limit-a[c].cost, c-1, s, f, w+a[c].weight);
			s.remove(s.size()-1);
			for(int i=0;i<diff.size();i++){
				f[diff.get(i)]=false;
			}
		}
		//not pickign the item and pass it on to the next recursion
		b(a, limit, c-1, s,f,w);
	}
}

class course{
	public String name;
	public int weight;
	public int cost;
	public int[] constraint;
	public course(String a, int b, int c, int[] d){
		name = a;
		weight = b;
		cost = c;
		constraint = d;
	}
}