Informatika gyűjtemény

Egy szinttel feljebb Megoldás

2004050607080910

<<  24. óra  >>

<<  Bevásárlás  >>

NézetNyomtat

Bevásárlás (Megoldás)
Szakkörök > BDG Szakkör > 2009/2010 > 24. óra
Címkék > Feladat
Versenyek > Google Code Jam > Practice Problems

Jegyzetek

A nullás bolt az origóban van, és nem árul semmit.
részfeladat[Bolt][TermékHalmaz] = a szűkséges költség, onnantól, hogy belépünk a 'Bolt' azonosítójú boltba, a 'TermékHalmaz' halmazban lévő áruk birtokában, odáig, hogy visszamegyünk a kiindulási állomásra
Eljárás RészKiszámol(Bolt, TermékHalmaz)
    Részkiszámol := Kombinál(Bolt, TermékHalmaz, TermékHalmaz, 0, Hamis)
Eljárás Vége

{Végigpróbálja minden termékhalmaz vásárlását}
Eljárás Kombinál(Bolt, RégiTermékHalmaz, TermékHalmaz, pos, Romlandó)
    Ha pos > MaxItems Akkor
        {Ha végignézte az összes terméket}
        Ha RégiTermékHalmaz = TermékHalmaz és Bolt > 0 Akkor
            {Ha nem vásárolt egy új terméket sem}
            Kombinál := VÉGTELEN;
        Különben
            Ha TermékHalmaz = ÖsszesTermék Akkor
                {Ha minden termék bekerült a halmazba}
                Kombinál:= Távolság(Bolt, 0)
            Különben
                {Még nincs minden termék a halmazban, a következő boltot végigpróbálgatjuk}
                Kombinál:= VÉGTELEN;
                Ciklus KövBolt:= 1-től MaxBolt-ig
                    Ha Bolt <> KövBolt Akkor
                        X:= RészKiszámol(KövBolt, TermékHalmaz)+Távolság(Bolt, KövBolt, Romlandó)
                        Ha X < Kombinál Akkor Kombinál := X;
                    Elágazás Vége
                Ciklus Vége
            Elágazás Vége
        Elágazás Vége
    Különben
        {Akutális terméket nem vesszük be}
        Kombinál := Kombinál(Bolt, KövBolt, TermékHalmaz, pos+1);
        Ha items[pos] = Hamis és bolt_items[bolt][pos] = Igaz Akkor
            {Akutális terméket bevesszük}
            Aktuális := Kombinál(Bolt, RégiTermékHalmaz,  TermékHalmaz + termék(pos), pos+1, Romlandó vagy romlandó[termék]);
            Ha Aktuális < Kombinál Akkor Kombinál := Aktuális;          
        Elágazás Vége
    Elágazás Vége
Eljárás Vége

Adatbekérés pascalban

shoppingplan.pas

Kódok

Fehér Gábor (pascal) fg_bevasarlas.pas
Fehér Gábor (java) fg_bevasarlas.java
Mezei Balázs (C++) mb_bevasarlas.cpp
Uray János (C++) uj_bevasarlas.cpp