Maximized Study

talk open source
1

The problem was in last year’s Trinity programming contest problems, and I’ve been trying for a few hours to get it to work just right. I’m very close, but I know of one bug (which I’ll let you try and find).

Here’s the Java source:

import java.util.*;
import java.io.*;

public class Problem2 {
	public static void main (String args[]) throws IOException {
		Scanner scanner = new Scanner (new FileReader("problem2.txt"));
		
		int numberOfCases = scanner.nextInt();

		for (int i=0; i<numberOfCases; i++) {
			scanner.nextLine();
			
			int bagCapacity = scanner.nextInt();
			int bagFull=0;
			
			int numBooks = scanner.nextInt();
			
			ArrayList<MyBook> books = new ArrayList<MyBook>(numBooks);
			
			for (int j=0; j<numBooks; j++) {
				books.add(new MyBook(scanner.next(), scanner.nextInt(), scanner.nextInt()));
			}
			
			Collections.sort(books);
			
			ListIterator<MyBook> iterator = books.listIterator();
			while (iterator.hasNext()) {
				MyBook book = iterator.next();
				if (book.weight+bagFull <= bagCapacity) {
					bagFull+=book.weight;
				} else {
					iterator.remove();
				}
			}

			System.out.println(MyBook.totalGradeValue(books));
		}
	}
}

class MyBook implements Comparable {
	String name;
	int weight;
	int gradeValue;
	double ratio;
	
	public MyBook (String name, int weight, int gradeValue) {
		this.name		= name;
		this.weight		= weight;
		this.gradeValue	= gradeValue;
		
		this.ratio = (double) gradeValue/weight;
	}
	
	public int compareTo (Object book) {
		return ((int)((MyBook)book).ratio-(int)this.ratio);
	}
	
	public String toString () {
		return this.name + " " + weight + " " +gradeValue;
	}
	
	public static int totalGradeValue (ArrayList<MyBook> books) {
		int total = 0;
		for (int i=0; i<books.size(); i++) {
			total += (books.get(i)).gradeValue;
		}
		
		return total;
	}
}

And here’s the sample file loaded in (you need to save this as problem2.txt to make the above file read it).

2
10 3
History 7 30
Math 4 40
English 6 30
10 2
CliffNotes 5 99
OfficialText 8 1

It’ll find the most it can bring home. The first line represents the number of cases following, and the first for each case represents the number of pounds available in your backpack, and the number of books to follow. Each book has its name, weight, and point value it’s help your score.

It’ll output:

70
99

For the 70 points you can get in the first set, and the 99 (with Cliffnotes) you can potentially get in the second set.

You have to get the most possible. :slight_smile:

Try and find my bug, and see if you can solve it.