Informatika gyűjtemény

Egy szinttel feljebb fg_bevasarlas.java

2004050607080910

<<  24. óra  >>

<<  Bevásárlás  >>

NézetNyomtat

fg_bevasarlas.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 5 KB
package shoppingplan;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;

public class MainEZ {
    int num_items, num_stores, price_of_gas;
    int store_x[];
    int store_y[];
    int store_prices[][];
    int store_codes[];
    boolean item_perishable[];
    String item_names[];
    int full_items;

    double solve_cache[][];
    double dist_price[][];

    void initPrices() {
        dist_price = new double[num_stores][num_stores];
        for (int i = 0; i < num_stores; i++) {
            for (int j = 0; j < num_stores; j++) {
                int dx = store_x[i]-store_x[j];
                int dy = store_y[i]-store_y[j];
                double dist = Math.sqrt(dx*dx+dy*dy);
                dist_price[i][j] = dist*price_of_gas;
            }
        }
    }

    double dist_price(int store1, int store2, boolean perish_flag) {
        if (store1 == store2) throw new RuntimeException();
        if (!perish_flag) return dist_price[store1][store2];
        else return dist_price[store1][0]+dist_price[store2][0];
    }

    double combine(int store, int items0, int items, int pos, boolean perish) {
        if (pos >= num_items) {
            if (items0 == items && store != 0) return Double.MAX_VALUE;
            if (items == full_items) {
                return dist_price(store, 0, false); //go home
            } else {
                double result = Double.MAX_VALUE;
                for (int next_store = 1; next_store < num_stores; next_store++) {
                    if (store == next_store) continue;
                    double cur = solve(next_store, items)+dist_price(store, next_store, perish);
                    if (cur < result) result = cur;
                }
                return result;
            }
        } else {
            double result = combine(store, items0, items, pos+1, perish);
            if ((items & (1<<pos)) == 0 && (store_codes[store] & 1<<pos) != 0) {
                double cur = store_prices[store][pos]+
                        combine(store, items0, items | 1<<pos, pos+1, perish || item_perishable[pos]);
                if (cur < result) result = cur;
            }
            return result;
        }
    }

    double solve(int store, int items) {
        if (solve_cache[store][items] >= 0) return solve_cache[store][items];
        solve_cache[store][items] = combine(store, items, items, 0, false);
        return solve_cache[store][items];
    }

    double solve() {
        solve_cache = new double[num_stores][full_items+1];
        for (int i = 0; i < num_stores; i++) {
            for (int j = 0; j < full_items+1; j++) {
                solve_cache[i][j] = -1;
            }
        }
        initPrices();
        return solve(0, 0);
    }

    void run() throws IOException {
        System.out.println("MainEZ");
   //     String code="small-practice";
        String code="large-practice";
        BufferedReader r = new BufferedReader(new FileReader(new File("D-"+code+".in")));
        FileWriter w = new FileWriter(new File("D-"+code+".out"));

        int n = Integer.parseInt(r.readLine());
        for (int i = 1; i <= n; i++) {
            String hdr[] = r.readLine().split(" ");
            num_items = Integer.parseInt(hdr[0]);
            num_stores = Integer.parseInt(hdr[1]);
            price_of_gas = Integer.parseInt(hdr[2]);
            num_stores += 1; //0. store is at (0, 0)

            store_x = new int[num_stores];
            store_y = new int[num_stores];
            store_prices = new int[num_stores][num_items];
            store_codes = new int[num_stores];
            item_perishable = new boolean[num_items];

            item_names = r.readLine().split(" ");
            for (int j = 0; j < num_items; j++) {
                if (item_names[j].charAt(item_names[j].length()-1) == '!') {
                    item_perishable[j] = true;
                    item_names[j] = item_names[j].substring(0, item_names[j].length()-1);
                }
            }

            full_items = (1<<num_items) - 1;

            store_x[0] = 0; store_y[0] = 0;
            for (int j = 1; j < num_stores; j++) {
                String store_desc[] = r.readLine().split(" ");
                store_x[j] = Integer.parseInt(store_desc[0]);
                store_y[j] = Integer.parseInt(store_desc[1]);
                for (int k = 2; k < store_desc.length; k++) {
                    String item[] = store_desc[k].split(":");
                    int item_id = 0;
                    while (item_id < num_items && !item[0].equals(item_names[item_id])) item_id++;
                    store_codes[j] |= 1<<item_id;
                    store_prices[j][item_id] = Integer.parseInt(item[1]);
                }
            }

            double sol = solve();

            String s = String.format("Case #%1$d: %2$.7f\n", i, sol);
            System.out.print(s);
            w.write(s);
        }
        w.close();
        r.close();
    }

    public static void main(String[] args) throws IOException {
        new MainEZ().run();
    }
}
(Vissza)