// Knapsack.java // Vytautas Malisauskas KTU IFM3/1 1998 // Knapsack.class // KnapSackDomain.class // KnapWeightProvider.class // KnapDataUrlProvider.class package lt.ktu.gmj.tasks; import lt.ktu.gmj.*; import lt.ktu.gmj.propertySheet.*; import java.net.*; import java.io.*; import java.util.*; import java.lang.*; //********************* Sprendimo funkcijos tasko srities apibrezimas ********** class KnapSackDomain extends Domain { static final String []dimensions= { "Monte Carlo", "Randomized Heuristics", "Greedy Heuristics" }; KnapSackDomain () { min[0] = min[1] = min[2]=0; max[0] = max[1] = max[2]=10; defaultPoint.x[0] = 5; //santykine tikimybe imti daikta pagal "Monte Carlo" defaultPoint.x[1] = 5; //-"- pagal "Randomized Heuristics" defaultPoint.x[2] = 5; //-"- pagal "Greedy Heuristics" } public String[] dimensions () { return dimensions; } }; //************************ Kuprines uzdavinio klase *************************** public class Knapsack implements Task { private double norm_point[]; //normalizuotas sprendimo funkcijos taskas private int number_of_objects; //bendras daiktu skaicius public double total_weight=10; //svoris, kuri galima paimti private int object_taken[]; //pozymiai ar i-tasis daiktas paimtas private float object_cost[]; //daiktu kainos private float object_weight[]; //daiktu svoriai private double object_ratio[]; //santykines daiktu kainos svorio vienetui private Random rnd = new Random(); //atsitiktiniu skaiciu generatorius public String data_url = new String("http://norveda.txt"); //duomenu failo URL private String data_url_old = new String(); //seno duomenu failo URL private KnapSackDomain mydomain = new KnapSackDomain(); //sprendimo funkcijos tasko reiksmiu sritis //************ Duomenu ivedimo metodas private void input() throws java.net.MalformedURLException,java.io.IOException { int i,k,num = 0; float f1,f2; String data_line; number_of_objects = 0; //----------------- Pasirenkame duomenu saltini URL tmyurl = new URL (data_url); System.out.println("Reading data from: "+tmyurl.getHost()+tmyurl.getFile()); //----------------- Nuskaitom is duomenu failo objektu kieki URLConnection tmycon = tmyurl.openConnection(); System.out.println("Data type: "+tmycon.getContentType()+" with size: "+tmycon.getContentLength()); InputStream tis = tmycon.getInputStream(); DataInputStream tids = new DataInputStream(tis); tids.readLine(); //pavadinimai while((data_line=tids.readLine()) != null) { StringTokenizer st = new StringTokenizer(data_line); st.nextToken(); st.nextToken(); number_of_objects += Integer.valueOf(st.nextToken()).intValue(); num++; } System.out.println("Object types: "+num+" and total ammount: "+number_of_objects); tids.close(); tis.close(); //----------------- Isskiriam atminti object_taken = new int[number_of_objects]; object_cost = new float[number_of_objects]; object_weight= new float[number_of_objects]; object_ratio = new double[number_of_objects]; //----------------- Nuskaitinejame duomenis URLConnection mycon = tmyurl.openConnection(); InputStream is = mycon.getInputStream(); DataInputStream ids = new DataInputStream(is); ids.readLine(); //pavadinimai num = 0; while((data_line = ids.readLine()) != null) { StringTokenizer st = new StringTokenizer(data_line); f1 = Float.valueOf(st.nextToken()).floatValue(); //svoris f2 = Float.valueOf(st.nextToken()).floatValue(); //kaina k = Integer.valueOf(st.nextToken()).intValue(); //kiekis for (i = 0; i < k; i++) { object_weight[num] = f1; object_cost [num] = f2; object_ratio [num] = f2 / f1; num++; } } ids.close(); is.close(); System.out.println("Data ready..."); } //********* Sprendimo funkcijos tasko normalizavimo metodas private void normalize (Point pt) { double sum = 0.; norm_point = new double[3]; for (int i = 0; i < 3; i++) sum += pt.x[i]; for (int i = 0; i < 3; i++) norm_point[i] = pt.x[i] / sum; } //********* Kainos funkcijos reiksmes skaiciavim metodas private double calculation() { int i,n; double weight = 0.; //paimtas svoris double cost = 0.; //paimtu daiktu kaina (kainos funkcijos reiksme) double maxh =-1.; //maksimali santykine kaina (heuristika) double hsum = 0.; //atvirstine heuristiku suma int maxi = 0; //maksimalios heuristikos indeksas //--------- Nustatome, kad visi daiktai nepaimti for ( i = 0; i < number_of_objects; i++) object_taken [i] = 0; //--------- Renkames daiktus is nepasirinktu for ( n= number_of_objects; n > 0; n--) { //----------- Randame daikta su didziausia heuristika for (i = 0; i < number_of_objects; i++) { if ((object_taken [i] == 0) && (maxh < object_ratio [i])) { maxh = object_ratio [i]; maxi = i; } } //----------- Randame heuristiku suma ir jai atvirkstine hsum=0.; for (i = 0; i < number_of_objects; i++) if (object_taken [i] == 0) hsum += object_ratio [i]; hsum = 1. / hsum; double eps = rnd.nextDouble(); // generuojame atsitikti skaiciu double r = 0.; //------------ Skaiciuojame randomizuota tolydine sprendimo funkcija for (i = 0; i < number_of_objects; i++) { if (object_taken [i] == 0) r += 1. / n * norm_point[0] + hsum * norm_point[1] * object_ratio [i] + norm_point[2] * (i == maxi ? 1 : 0); if (r > eps ) { //----------- patenkinus sprendimo funkcija imame einamaji daikta weight += object_weight [i]; if (weight > total_weight) return -cost; cost += object_cost [i]; object_taken [i] = 1; break; } } } return -cost; // graziname neigiama kaina,nes paketas minimizuoja } //************ Sprendimo funkcijos tasko reiksmiu srities pateikimo metodas public Domain domain () { return mydomain; } //************ Kintamuju ivedimo metodas public void customize (PropertyManager manager) { //-------- Iveda maksimalu paimama svori ribose nuo 10 iki 10000 manager.add ( new DoubleProperty("Total Weight", new KnapWeightProvider (this), 10, 10000)); //-------- Iveda duomenu failo URL manager.add ( new UrlProperty("URL of data file", new KnapDataUrlProvider (this))); } //**** Metodas pateikianis suskaiciuota kainos funkcija uzduotame sprendimo funkcijos taske public double f (Point pt) { normalize (pt); // normalizuojame taska if (!data_url.equals(data_url_old)) // tikriname ar buvo pakeistas URL { try { input(); // ivedame duomenis data_url_old=new String(data_url); } catch(Exception e) { System.out.println("!!!-Bad data: "+e); } } return calculation(); // graziname kainos funkcijos reiksme } }; //********** Svorio kintamojo ivedimo klase ********************************* class KnapWeightProvider extends SimplePropertyProvider { public Knapsack knap; public KnapWeightProvider (Knapsack _knap) { knap=_knap; } public Object get () { return new Double(knap.total_weight); } public void set (Object value) throws InvalidPropertyException { knap.total_weight=((Double)value).doubleValue(); } }; //*********** Duomenu failo URL kintamojo ivedimo klase *********************** class KnapDataUrlProvider extends SimplePropertyProvider { public Knapsack knap; public KnapDataUrlProvider (Knapsack _knap) { knap=_knap; } public Object get () { return knap.data_url; } public void set (Object value) throws InvalidPropertyException { knap.data_url=new String(value.toString()); } };