Informatika gyűjtemény

Egy szinttel feljebb uj_bevasarlas.cpp

2004050607080910

<<  24. óra  >>

<<  Bevásárlás  >>

NézetNyomtat

uj_bevasarlas.cpp (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: utf-8
Méret: 4 KB
/*
    Informatika algoritmus szakkör
    Feladat: Bevásárlás
    Forrás: http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0910/24ora/shoppingplan
    Uray M. János, 2010. április 13.
*/
#include <fstream>
#include <iomanip>
#include <cstdlib>
#include <string>
#include <cmath>
using namespace std;

#ifndef INFINITY
#include <limits>
#define INFINITY numeric_limits<float>::infinity()
#endif

#define MaxItems 15
#define MaxStores 50

typedef unsigned char byte;
typedef unsigned short int word;
typedef unsigned long int dword;
typedef unsigned long long int qword;

// Az üzletek
struct sStore {
    // Koordináta
    int X, Y;
    // Az egyes termékek ára (-1, ha nincs ilyen termék)
    double Price[MaxItems];
    // Bitmező az egyes termékekről
    word Items;
} Store[MaxStores];
// A termékek
struct sItem {
    // Romlandó-e
    bool bPerishable;
    // Név
    string Name;
} Item[MaxItems];
// A termékek és az üzletek száma, ill. a benzin ára (price of gas)
int nItems, nStores, POG;
// A dinamikus programozáshoz használt tömb
double State[MaxStores][1 << MaxItems];
// Bitmaszk az összes áruról
word AllItems;

void ReadItemDatas (ifstream &, sItem &);
void ReadStoreDatas (ifstream &, sStore &);

double Dist (int, int, bool);
double BestPrice (void);
double BestPrice (byte, word);

int main (int nArgs, char * Arg []) {
    int N, I, J, K;
    // Argumentumok ellenőrzése, fájlok megnyitása
    if (nArgs < 3)
        return 1;
    ifstream IF(Arg[1]);
    ofstream OF(Arg[2]);
    if (IF == NULL || OF == NULL) {
        IF.close();
        OF.close();
        return 1;
    }
    // A tesztesetek
    IF >> N;
    for (I = 0; I < N; I++) {
        // Állományból olvasás
        IF >> nItems >> nStores >> POG;
        AllItems = (1 << nItems) - 1;
        for (J = 0; J < nItems; J++)
            ReadItemDatas(IF, Item[J]);
        for (J = 0; J < nStores; J++)
            ReadStoreDatas(IF, Store[J]);
        // A rekurzió indítása
        OF << "Case #" << I + 1 << ": " << setprecision(7) << fixed << BestPrice() << endl;
    }
    // Fájlok bezására, kilépés
    IF.close();
    OF.close();
    return 0;
}

// Termék beolvasása
void ReadItemDatas (ifstream & IF, sItem & Item) {
    IF >> Item.Name;
    Item.bPerishable = Item.Name.find_first_of('!') < Item.Name.length();
    if (Item.bPerishable)
        Item.Name = Item.Name.substr(0, Item.Name.length() - 1);
}
// Üzlet beolvasása
void ReadStoreDatas (ifstream & IF, sStore & Store) {
    int A, B, C, I;
    string Items, IN_PR, IN;
    int PR;
    // Koordináták
    IF >> Store.X >> Store.Y;
    // Nevek stringje (a sor végéig)
    getline(IF, Items);
    A = Items.find_first_of(' ') + 1;
    for (I = 0; I < nItems; I++)
        Store.Price[I] = -1;
    Store.Items = 0;
    // String szétszedése darabokra
    do {
        B = Items.find_first_of(' ', A);
        if (B >= Items.length())
            B = Items.length();
        IN_PR = Items.substr(A, B - A);
        C = IN_PR.find_first_of(':');
        IN = IN_PR.substr(0, C);
        for (I = 0; I < nItems; I++)
            if (Item[I].Name == IN) {
                Store.Price[I] = atof(IN_PR.substr(C + 1).c_str());
                Store.Items |= 1 << I;
            }
        A = B + 1;
    } while (B < Items.length());
}

// A és B üzlet közötti "távolság" (ha bPerishable, akkor közben hazamegyünk)
double Dist (int A, int B, bool bPerishable) {
    return bPerishable ?
        hypot(Store[A].X, Store[A].Y) + hypot(Store[B].X, Store[B].Y) :
        hypot(Store[A].X - Store[B].X, Store[A].Y - Store[B].Y);
}

// A rekurzió indításáért felelős függvény
double BestPrice (void) {
    double Q = INFINITY, P;
    int I, J;
    for (I = 0; I < nStores; I++)
        for (J = 0; J < (1 << nItems); J++)
            State[I][J] = 0;
    for (I = 0; I < nStores; I++) {
        P = hypot(Store[I].X, Store[I].Y) * POG + BestPrice(I, AllItems);
        if (P < Q)
            Q = P;
    }
    return Q;
}
// Rekurzív függvény: bemegyünk az S üzletbe úgy, hogy az
// Items termékeket kell még megvenni
double BestPrice (byte S, word Items) {
    // Dinamikus programozás
    if (State[S][Items] != 0)
        return State[S][Items];
    // W: a boltban beszerezhető hiányzó termékek
    // X: valamely részhalmaza W-nek
    // It_: a következő boltba való betéréskor a még hiányzó termékek
    word W = Items & Store[S].Items, X, It_;
    int I;
    bool bPer;
    double Q = INFINITY, Price0, Price;
    
    // Előállítjuk az összes értelmes bevásárlást az S boltban
    for (X = 1; X <= W; X++) {
        // X csak W részhalmaza lehet
        if (X & ~W)
            continue;
        It_ = Items & ~X;
        // A termékek ára és a romlandóság eldöntése
        Price0 = 0;
        bPer = false;
        for (I = 0; I < nItems; I++)
            if ((X >> I) & 1) {
                Price0 += Store[S].Price[I];
                bPer = bPer || Item[I].bPerishable;
            }
        // A következő bolt kiválasztása (vagy hazatérés, ha mindent megvettünk)
        if (It_ == 0) {
            Price = Price0 + hypot(Store[S].X, Store[S].Y) * POG;
            if (Price < Q)
                Q = Price;
            break;
        }
        for (I = 0; I < nStores; I++)
            if (S != I && (Store[I].Items & It_)) {
                Price = Price0 + Dist(S, I, bPer) * POG + BestPrice(I, It_);
                if (Price < Q)
                    Q = Price;
            }
    }
    return State[S][Items] = Q;
}
(Vissza)