/*
 * 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 Brute {
    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 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 boolean isAcceptable(int[] weights, boolean[] presence, int maxWeight){
        int weightsSum = 0;
        for (int i = 0; i < weights.length; i++) {
            // if(presence[i]) weightsSum += weights[i];
        }
        //System.out.println(weightsSum);
        return (weightsSum <= maxWeight);
    }
     */
    
    static void tryNext(int itemIndex, int currentWeight, int currentPrice){
        if (itemIndex < bestSolution.length){
            //aktualni prvek neni v konfiguraci
            actualConfiguration[itemIndex] = false;
            tryNext(itemIndex + 1, currentWeight, currentPrice);
            
            //aktualni prvek je v konfiguraci
            if((currentWeight + v[itemIndex]) <= maxWeight){ //pokud se do batohu jeste vejde
                actualConfiguration[itemIndex] = true;
                tryNext(itemIndex + 1, currentWeight + v[itemIndex], currentPrice + c[itemIndex]);
                
                if ((currentPrice + c[itemIndex]) > bestPrice) {
                    bestPrice = currentPrice + c[itemIndex];
                    System.arraycopy(actualConfiguration,0,bestSolution,0,actualConfiguration.length);
                    
                }
            }
        }
    }
    
    static void BruteThread(String[] args){
        tryNext(0,0,0);    
    }
    
    /**
     * @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_25.txt";
        String [] inFile = (args[0]).split("\\.");
        String mySolutionFileString = "solution/" + inFile[0] + "_sol_brute." + inFile[1];
        String myTimesFileString = "solution/" + inFile[0] + "_tim_brute." + 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);
            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];
                cDIVv = new long[size];
                actualConfiguration = new boolean[size];
                bestSolution = new boolean[size];
                int i = 0;
                while (sScan.hasNext()) {
                    v[i] = sScan.nextInt();
                    c[i] = sScan.nextInt();
                    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("");
        
    }
    
}