/*
 * Brute.java
 *
 * Created on 1.10.2007, 23:52:22
 *
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package knapsack;

import java.io.*;
import java.io.File;
import java.io.FileOutputStream;
import java.util.Scanner;
import java.util.Arrays;

/**
 * X36PAA - zimni semestr 2007, uloha cislo 1 - batoh - brute force
 * @author Petr Chytil
 */
public class SimpleHeuristic {

    static int maxWeight,  bestPrice,  bestWeight,  id,  size;
    //static int[] v; // pole vah jednotlivych veci = {11,7,5,4,3,3,3,2,2,2,2,1};
    //static int[] c; // pole cen= {20,10,11,5,25,50,15,12,6,4,5,30};
    static Item[] items;
    //public static long[] cDIVv; // pomer cena/vaha pro jednotlive veci
    static boolean[] bestSolution;// = new boolean[12]; // = {0,0,0,0,0,0,0,0,0,0,0,0}
    static boolean[] actualConfiguration;
    static long startTime,  endTime;
    static FileOutputStream mySolutionFile;
    static FileOutputStream myTimesFile;
    static PrintStream printToSolutionsFile;
    static PrintStream printToTimesFile;

    static private class Item implements Comparable {

        int v, c;
        int defaultPosition;
        long cDIVv;

        public Item(int v, int c, int defaultPosition) {
            this.v = v;
            this.c = c;
            this.defaultPosition = defaultPosition;
            this.cDIVv = c / v;
        }

        public int compareTo(Object o) {

            return Double.compare(this.cDIVv, ((Item) o).cDIVv);
        }
    }

    static void simpleHeuristic() {
        Arrays.sort(items);
    //    for (int i = 0; i < items.length; i++) {
    //        System.out.print("[" + items[i].cDIVv + ";" + items[i].defaultPosition + "]");
    //    }
    //    System.out.println("");
        int currentWeight = 0;
        int i = items.length - 1;
        while ((i >= 0 ) && ((currentWeight + items[i].v) <= maxWeight)) {
            currentWeight += items[i].v;
            bestPrice += items[i].c;
            bestSolution[items[i].defaultPosition] = true;
            i--;

        }

    }

    static void SimpleHeuristicThread(String[] args) {
        simpleHeuristic();
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        //maxweight = 20;
        bestPrice = 0;
        bestWeight = 0;
        args = new String[3];
        args[0] = "knap_40.txt";
        String [] inFile = (args[0]).split("\\.");
        String mySolutionFileString = "solution/" + inFile[0] + "_sol_heur." + inFile[1];
        String myTimesFileString = "solution/" + inFile[0] + "_tim_heur." + inFile[1];
        try {
            BufferedReader instancesFile = new BufferedReader(new FileReader(args[0]));
            mySolutionFile = new FileOutputStream(mySolutionFileString);
            myTimesFile = new FileOutputStream(myTimesFileString);
            printToSolutionsFile = new PrintStream(mySolutionFile);
            printToTimesFile = new PrintStream(myTimesFile);
            //BufferedReader instancesFile = new BufferedReader(new FileReader(args[0]));
            //mySolutionFile = new FileOutputStream("solution/my_knap_10h.txt");
            //myTimesFile = new FileOutputStream("solution/times_knap_10h.txt");
            //printToSolutionsFile = new PrintStream(mySolutionFile);
            //printToTimesFile = new PrintStream(myTimesFile);
            String s,
             s2 = new String();
            Brute bruteInst = new Brute();
            while ((s = instancesFile.readLine()) != null) {
                //s = instancesFile.readLine();
                s2 += s + "\n";
                //System.out.println(s);
                Scanner sScan = new Scanner(s);
                id = sScan.nextInt();
                //System.out.printToSolutionsFile(id + " ");
                size = sScan.nextInt();
                //System.out.printToSolutionsFile(size + " ");
                maxWeight = sScan.nextInt();
                //System.out.println(maxweight + " ");
                //v = new int[size];
                //c = new int[size];
                items = new Item[size];
                //cDIVv = new long[size];
                actualConfiguration = new boolean[size];
                bestSolution = new boolean[size];
                int i = 0;
                while (sScan.hasNext()) {
                    items[i] = new Item(sScan.nextInt(), sScan.nextInt(), i);
                    i++;
                }
                Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
                // zacatek mereni
                startTime = System.nanoTime();
                //bruteInst.BruteThread(args);
                SimpleHeuristicThread(args);
                // konec mereni
                endTime = System.nanoTime();
                //printIt();
                writeItToFile();
                //System.out.println(endTime-startTime);
                bestWeight = 0;
                bestPrice = 0;
            }
            instancesFile.close();
            printToSolutionsFile.close();
            printToTimesFile.close();
            mySolutionFile.close();
            myTimesFile.close();
        } catch (IOException ex) {
            ex.printStackTrace();
        }


    }

    public static void writeItToFile() {

        printToSolutionsFile.print(id + " " + size + " " + bestPrice + "  ");
        for (int i = 0; i < bestSolution.length; i++) {
            if (bestSolution[i]) {
                printToSolutionsFile.print("1");
            } else {
                printToSolutionsFile.print("0");
            }
            if (i != (bestSolution.length - 1)) {
                printToSolutionsFile.print(" ");
            }
        }
        printToSolutionsFile.println("");
        printToTimesFile.println(size + " " + (endTime - startTime));

    }

    public static void printIt() {
        //System.out.println("Final price:" + bestPrice );
        //System.out.println("Final weight:" + bestWeight );
        System.out.print(id + " " + bestPrice + " ");
        for (int i = 0; i < bestSolution.length; i++) {
            if (bestSolution[i]) {
                System.out.print("1");
            } else {
                System.out.print("0");
            }
            if (i != (bestSolution.length - 1)) {
                System.out.print(" ");
            }
        //System.out.printToSolutionsFile(bestSolution[i] + " ");
            //System.out.printToSolutionsFile("w:" + v[i] + " ");
            //System.out.println("p:" + c[i] + " ");
        }
        System.out.println("");

    }
}