import java.util.Scanner; import java.io.*; /* * Lab 6 * * Author: Robin Dawes * * Date: 20081102 * * Comment: * */ public class Billboards { static int instances; static int numOfLocations; static Spot[] locations; static int[][] table; public static void main (String[] argv) throws Exception { Scanner myScanner = new Scanner(new File("Lab_6_Data.txt")); // find out how many instances instances = myScanner.nextInt(); for (int i = 0; i < instances; i++) { System.out.println("\nInstance " + i + " input: "); numOfLocations = myScanner.nextInt(); locations = new Spot[numOfLocations]; for (int d = 0; d < numOfLocations; d++){ locations[d] = new Spot(myScanner.nextDouble()); System.out.format("%10.1f",locations[d].getDistance()); } System.out.println(); for (int d = 0; d < numOfLocations; d++){ locations[d].setValue(myScanner.nextInt()); System.out.format("%11d",locations[d].getValue()); } System.out.println("\n"); // sort the locations based on the distance value locations = HeapSort(locations); for (int d = 0; d < numOfLocations; d++) System.out.format("%10.1f",locations[d].getDistance()); System.out.println(); for (int d = 0; d < numOfLocations; d++){ System.out.format("%11d",locations[d].getValue()); } System.out.println("\n"); table = new int[numOfLocations][numOfLocations+1]; /* * table[i][j] is the maximum obtainable profit using locations [0..i] without getting within 5 km of locations[j].distance * * the last column is for distance "infinity" */ // fill in the first row of the table for (int j = 0; j < numOfLocations; j++) { if (locations[0].getDistance() + 5 <= locations[j].getDistance()) table[0][j] = locations[0].getValue(); else table[0][j] = 0; } table[0][numOfLocations] = locations[0].getValue(); // fill in the rest of the table for (int r = 1; r < numOfLocations; r++) { for (int c = 0; c < numOfLocations; c++) { if (locations[r].getDistance() + 5 > locations[c].getDistance()) table[r][c] = table[r-1][c]; else { table[r][c] = Math.max(table[r-1][c], locations[r].getValue() + table[r-1][r]); } } // last column treated separately since distance test is not needed table[r][numOfLocations] = Math.max(table[r-1][numOfLocations], locations[r].getValue() + table[r-1][r]); } for (int r = 0; r < numOfLocations; r++) { for (int c = 0; c <= numOfLocations; c++) { System.out.format("%11d",table[r][c]); } System.out.println(); } // trace back to find solution System.out.println("Solution:"); printSol(locations, table, numOfLocations-1, numOfLocations); System.out.println(); } } // main static void printSol(Spot[] locs, int[][] t, int curRow, int curCol) { if ((curRow == 0) && (t[curRow][curCol] > 0)) System.out.format("%10.1f",locations[curRow].getDistance()); else if ((curRow > 0) && (curCol >= 0) && (t[curRow][curCol] > 0)) { if (t[curRow][curCol] == locs[curRow].getValue() + t[curRow-1][curRow]) { printSol(locs,t,curRow-1,curRow); System.out.format("%10.1f",locations[curRow].getDistance()); } else printSol(locs,t,curRow-1,curCol); } } //printSol(Spot[], int[][], int, int) static Spot[] HeapSort(Spot[] locs) { int len = locs.length; //double flagVal = chooseFlag(locs); locs = heapify(locs); Spot[] sorted = new Spot[len]; for (int i = 0; i < len; i++) sorted[i] = extractMin(locs); return sorted; } // Heapsort(Spot[]) static Spot[] heapify(Spot[] locs){ for (int i = 1; i < locs.length; i++) { int temp = i; int tempParent = (temp - 1) / 2; while ((temp > 0) && (locs[temp].getDistance() < locs[tempParent].getDistance())) { swap(locs, temp, tempParent); temp = tempParent; tempParent = (temp - 1) / 2; } // while } // for return locs; } // heapify(Spot[]) static void swap(Spot[] locs, int a, int b){ Spot t = locs[a]; locs[a] = locs[b]; locs[b] = t; } // swap(Spot[], int,int) static Spot extractMin(Spot[] locs){ Spot returnVal = locs[0]; promote(locs, 0); return returnVal; } // extractMin(Spot[]) static void promote(Spot[] locs, int c) { /* * This can be done iteratively, but I'm doing it recursively just for the joy of it * * Chooses the smaller of c's children, moves it up to position c, then recurses on the * promoted child's position */ int n = locs.length; if (c > n-1) return; // we have fallen off the bottom of the tree if (locs[c] == null) return; // we have reached an empty node if (2*c + 1 > n - 1) { //this node is too close to the bottom of the tree to have children locs[c] = null; // mark this node as empty and do nothing more } else { // at least one child is possible, so examine them and choose the smaller one Spot leftChild = locs[2*c + 1]; Spot rightChild = null; if (2*c + 2 < n) rightChild = locs[2*c + 2]; // leftChild and rightChild now contain pointers if there are children, // and each contains null if the corresponding child is empty or non-existent if (rightChild == null) { locs[c] = leftChild; promote(locs, 2*c + 1); } else if (leftChild == null) { locs[c] = rightChild; promote(locs, 2*c + 2); } else if (leftChild.getDistance() <= rightChild.getDistance()) { locs[c] = leftChild; promote(locs, 2*c + 1); } else { locs[c] = rightChild; promote(locs, 2*c + 2); } } } // promote(Spot[],int) } // BillBoards class