Skip to content

Instantly share code, notes, and snippets.

@chaoxu
Created June 30, 2010 04:06
Show Gist options
  • Save chaoxu/458227 to your computer and use it in GitHub Desktop.
Save chaoxu/458227 to your computer and use it in GitHub Desktop.
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment