Zadání:
E-shop posílá zboží zákazníkům tak, že každý kus zboží zabalí do právě 1 krabice. Za tuto krabici se pak platí poštovné podle objemu krabice. Na vstupu dostaneme údaje o všech prodaných zboží za minulý rok a naším úkolem je navrhnout rozměry 2 druhů krabic tak, aby se v nich dalo posílat veškeré zboží a zároveň aby e-shop zaplatil co nejméně za poštovné.
Vstup:
D...počet druhů zboží
Pro každý druh zboží počet kusů, které se loni prodalo a trojice čísel xyz což jsou rozměry zboží.
Výstup:
(x1,y1,z1), N1
(x2,y2,z2), N2
kde xyz jsou rozměry krabice a N je číslo udávající kolik krabic tohoto druhu si má e-shop nechat vyrobit.
Upřesnění a omezení:
Rozměrem zboží se myslí nejmenší krabice, do které se vejde. Okraje krabice zanedbáváme. Např. pokud zboží má rozměry 2x3x6, tak se vejde do krabice 2x3x6 nebo větší.
Rozměry jsou v milimetrech v rozsahu 5 až 2000.
Zboží můžeme různě překlápět. (otáčet kolem různých os o 90 stupňů).
D <= 100 (max 100 různých druhů zboží)
Počet všech kusů zboží je nejvýše 10^9
Povolená paměť je 4GB
Místa na disku neomezeně, ale neplýtvat.
Čas běhu programu by měl být hodiny až několik dní.
Moje řešení:
Nejdřív jsem si řekl, že pokud potřebuju, aby se dalo poslat veškeré zboží, tak jedna krabice bude určitě muset mít 1 rozměr rovno maximu ze všech čísel x, y, z ze vstupu. Prostě pokud všechno zboží bude mít rozměry já nevím 3x4x4, ale 1 druh bude mít 2000x1x1, tak stejně potřebuju krabici, která má 1 z rozměrů 2000 mm.
Pokud bych měl za úkol najít jen 1 krabici, tak by to bylo triviální (popsáno níže). Řekl jsem si tedy, že si druhy zboží rozdělím do 2 skupin a pro každou tu skupinu už jednoduše najdu potřebné rozměry. Pak vyzkouším tolik možných rozdělení do skupin kolik dokážu a vypíšu nejlepší nalezené řešení. Tady je nejtěžší zjistit, jak rozdělit zboží, protože možných rozdělení je hodně. Rozhodl jsem se dělit zboží podle velikosti jejich největší hrany.
Udělám si nějaký struct, např.
struct Zbozi
{
int X;
int Y;
int Z;
int pocet;
}
Připravím si pole o max 100 prvcích typu Zbozi - pojmenuju si to pole třeba P. Načtu si vstup. Při načítání si rovnou spočítám parametr V, což je: (objem daného zboží * počet kusů) sečtené přes všechny druhy zboží. Toto číslo vlastně znát ani nepotřebuju, ale dává to jakousi míru a kontrolu, jak dobré je moje řešení a jestli je správné. Kdyby se mi náhodou povedlo najít řešení, které se rovná V, tak můžu rovnou skončit a vypsat rozměry. Kdybych našel řešení, které je menší než V, tak někde musí být chyba.
Projdu P a přeuspořádám si u každého zboží čísla tak, aby ten největší rozměr byl X. Př.: zboží d1 má rozměry 2x10x7. Tedy d1.X == 2, d1.Y == 10 a d1.Z == 7. Přeuspořádám takto: d1.X = 7; d1.Y = 2; a d1.Z = 7; (všechno zboží si pomyslně otočím nejdelší stranou na délku).
Pole P setřídím vzestupně podle X.
For i od 1 do velikosti P (tedy max 100) dělám:
Spočítám si rozměry krabice pro všechno zboží od P[1] do P[i-1] a pro zboží od P do P[100] (proměnná i dělí zboží na 2 skupiny).
Spočítám si S = (objem krabice 1 skupiny * počet kusů zboží v 1. skupině) + (objem krabice 2. skupiny * počet kusů zboží v 2. skupině).
Porovnám S s V, jestli jsem náhodou nenašel ideální řešení. Pokud ne, porovnám S s předchozím S. Pokud je menší, tak si zapamatuju současné S, rozměry krabic a proměnnou i a počet kusů v každé skupině (tj. N1 a N2 ze zadání).
Na konci pak vypíšu to, co jsem našel.
Jak jsem hledal rozměr krabice ve skupině:
Jeden ze tří rozměrů krabice určitě musí být největší X, protože jsem si to tak uložil do P. Zbylé rozměry zjistím snadno. Prostě najdu největší Y a největší Z u všech zboží ve skupině. Tedy pokud hledám rozměry v i-tém průchodu for cyklem v 1 skupině, tak:
krabice.X musí být P[i-1].X
krabice.Y bude maximum ze všech P[k].Y, kde k jde od 1 do i-1. Podobně krabice.Z bude maximum ze všech P[k].Z, kde k jde od 1 do i-1.
Čas a paměť si snadno spočítáte.
Pan Holan mi řekl, že můj program určitě nenajde nejlepší řešení, což je pravda, protože procházím velmi malou podmnožinu všech dělení do 2 skupin, ale líbilo se mu to na 1 až 2. Dal mi otázku na AVL stromy. Vložit několik prvků do stromu. Zkazil jsem dvojitou rotaci. Pak se zeptal, kolikrát nejvýše musím provést rotaci, když vkládám nebo odstraňuju. Řekl jsem, že když vkládám, tak log(n), protože to může jít až do kořene. To není pravda. Při vkládání pokud se mi pokazí výška, tak musím udělat jen buď jednoduchou rotaci nebo dvojitou. Při odstraňování musím dělat víc (potenciálně až do kořene). Ještě se mě zeptal na dolní odhad složitosti třídění porovnáváním. To jsem řekl správně, takže mi nakonec dal za 1.
Zkouška 10. 6. 2019 [T. Holan]
Pokračování základního kursu programování pro studenty 1. ročníku bakalářského studia informatiky a učitelství informatiky. Výuka bezprostředně navazuje na předmět PRG030 Programování I výkladem dalších algoritmů a jejich programové realizace, postupů a technik užívaných při tvorbě programů. Posluchači se seznámi se základy objektového programování a práce v současných vývojových prostředích. Předpokládají se vstupní znalosti v rozsahu předmětu PRG030 Programování I.
-
- Matfyz(ák|ačka) level I
- Příspěvky: 2
- Registrován: 20. 5. 2023 15:23
- Typ studia: Informatika Bc.
Re: Zkouška 10. 6. 2019 [T. Holan]
Příspěvek od vitSkalicky »
2. 5. 2023 Holan a Pergel - Stejné zadání, ale jen 5 MB paměti a upřesnění, že data o objednávkách z minulého roku jsou ve formátu XML (a nevejdou se do paměti) na což stačí říct, že použijete vhodný XML parser, který to umí zpracovávat proudově jeden záznam po druhém.
Nejrychlejší algoritmus je asi O(d³), ale O(d⁶) se taky dá obhájit. (d je počet různých druhů zboží)
Nejrychlejší algoritmus je asi O(d³), ale O(d⁶) se taky dá obhájit. (d je počet různých druhů zboží)
Zpět na „PRG031 Programování II“
Přejít na
- Aktuální informace
- ↳ Studijní oddělení
- ↳ Knihovna
- ↳ Studentská komora Akademického senátu (SKAS)
- ↳ Volby na ak. rok 2013/2014
- Všichni
- ↳ Práce
- ↳ Klubovna
- ↳ Toto fórum
- ↳ Státní závěrečná zkouška
- ↳ Bakalářské SZZ
- ↳ Magisterské SZZ
- ↳ Info for foreign students
- ↳ Akce
- ↳ Fotbalový turnaj 2008
- Informatika ZS
- ↳ Výuka ZS 1. ročník
- ↳ DMI002 Diskrétní matematika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI054 Matematická analýza I
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI057 Lineární algebra I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG030 Programování I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ SWI087 Principy počítačů
- ↳ Ostatní
- ↳ DMI051 Úvod do řešení problémů kombinatorických, mat. i jiných (IPS) II
- ↳ Výuka ZS 2. ročník
- ↳ MAI056 Matematická analýza III
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ OFY016 Fyzika pro nefyziky I - Svět kolem nás
- ↳ SWI089 Ochrana informace I
- ↳ SWI096 Internet
- ↳ TIN061 Algoritmy a datové struktury II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Aplikační software
- ↳ NPRG035 Jazyk C# a platforma .NET
- ↳ NPRG041 Programování v C++
- ↳ AIL062 Výroková a predikátová logika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ PGR013 Java
- ↳ MAI059 Pravděpodobnost a statistika
- ↳ Výuka ZS 3. ročník
- ↳ SWI099 Administrace Systemu Windows
- ↳ SWI015 Programování v Unixu
- ↳ SWI098 Principy překladačů
- ↳ 2006
- ↳ Ostatní
- ↳ DBI007 Organizace a zpracování dat I
- ↳ 2006
- ↳ MAI062 Algebra I
- ↳ PGR003 Počítačová grafika I
- ↳ SWI090 Počítačové sítě I
- ↳ Výuka ZS NMgr.
- ↳ TIN066 Datové struktury I
- ↳ TIN062 Složitost I
- ↳ TIN064 Vyčíslitelnost I
- ↳ MAI060 Pravděpodobnostní metody
- ↳ SWI004 Operační systémy
- ↳ SWI106 Administrace Unixu
- ↳ Ostatní
- ↳ NTIN090 Základy složitosti a vyčíslitelnosti
- ↳ OPT042 Programování s omezujícími podmínkami
- ↳ AIL002 Neuronové sítě
- ↳ AIL025 Evoluční algoritmy I
- ↳ AIL069 Umělá inteligence I
- ↳ NDBI001 Dotazovací jazyky I
- ↳ TIN070 Testování software
- ↳ NDBI027 Datové sklady a analytické metody pro Business Intelligence
- ↳ NDBI034 Vyhledávání multimediálního obsahu na webu
- ↳ NPRG023 Softwarový projekt
- Informatika LS
- ↳ Výuka LS 1. ročník
- ↳ MAI055 Matematická analýza II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI058 Lineární algebra II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG031 Programování II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ TIN060 Algoritmy a datové struktury I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI095 Úvod do UNIXu
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Výuka LS 2. ročník
- ↳ SWI071 Ochrana informace II
- ↳ TIN071 Automaty a gramatiky
- ↳ PRG033 Ročníkový projekt - specifikace
- ↳ DMI011 Kombinatorika a grafy I
- ↳ DBI025 Databázové systémy
- ↳ Ostatní
- ↳ SWI036 Programování pro Windows I & II
- ↳ SWI096 Internet
- ↳ PRG005 Neprocedurální programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ NSWI143 Architektura počítačů
- ↳ Výuka LS 3. ročník
- ↳ Ostatní
- ↳ PGR004 Počítačová grafika II
- ↳ PRG036 Technologie XML
- ↳ SZZ026 Bakalářská práce
- ↳ PRG003 Metodika programování a filozofie programovacích jazyků
- ↳ MAI064 Matematické struktury
- ↳ MAI042 Numerická matematika
- ↳ SWI021 Počítačové sítě II
- ↳ SWI045 Rodina protokolů TCP/IP
- ↳ NPRG038 Pokročilé programování pro .NET
- ↳ Výuka LS NMgr.
- ↳ SWI109 Konstrukce překladačů
- ↳ NPRG042 Programování v paralelním prostředí
- ↳ SWI117 Technologie vývoje webových aplikací
- ↳ SWI026 Softwarové inženýrství
- ↳ MAI061 Metody matematické statistiky
- ↳ I1 Ostatní Teoretická informatika
- ↳ I2 Ostatní Softwarové systémy
- ↳ I3 Ostatní Matematická lingvistika
- ↳ I4 Ostatní Diskrétní modely a algoritmy
- ↳ AIL026 Evoluční algoritmy II
- ↳ AIL070 Umělá inteligence II
- ↳ NDBI010 Dokumentografické informační systémy
- ↳ NDBI023 Dobývání znalostí
- ↳ NDBI016 Transakce
- ↳ NDBI006 Dotazovací jazyky II
- ↳ NAIL029 Strojové učení
- Matematika
- ↳ Výuka LS 1. ročník
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- ↳ Volitelné předměty
- ↳ Výuka LS 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Funkcionální analýza I
- ↳ Vybrané partie z funkcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Ostatní
- ↳ LS - Předměty MMIB a pokročilé Algebry
- ↳ Všeobecná diskuse
- ↳ Počítačová algebra
- ↳ Teorie čísel a RSA
- ↳ Aplikovaná kryptografie II
- ↳ Standardy v kryptografii
- ↳ Kryptoanalytické útoky
- ↳ Aplikace bezpečnostních mechanismů
- ↳ Kvantové a DNA počítače
- ↳ Faktorizace velkých čísel
- ↳ Algebraická geometrie v kladné charakteristice
- ↳ Výuka ZS 1. ročník
- ↳ MAA001 Matematická analýza 1a
- ↳ PRM044 Programování I
- ↳ MAA079 Proseminář z kalkulu 1a
- ↳ DMA005 Diskrétní matematika
- ↳ ALG001 Lineární algebra a geometrie I
- ↳ Ostatní
- ↳ Volitelné předměty
- ↳ Výuka ZS 2. ročník
- ↳ MIB
- ↳ Matematická analýza 2a
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Předměty finanční matematiky
- ↳ Ostatní
- ↳ Výuka ZS 3. ročník
- ↳ Matematická statistika
- ↳ Teorie pravděpodobnosti
- ↳ Náhodné procesy
- ↳ Optimalizace
- ↳ Předměty numeriky
- ↳ Předměty finanční matematiky
- ↳ Komplexní analýza
- ↳ Funcionální analýza
- ↳ Ostatní
- ↳ ZS - předměty MMIB a pokročilé Algebry
- ↳ Úvod do algebry
- ↳ Složitost pro kryptografii
- ↳ Samoopravné kódy
- ↳ Teoretická kryptografie
- ↳ Aplikovaná kryptografie I
- ↳ Datové a procesní modely
- ↳ Eliptické křivky
- ↳ Členění kryptografických standardů
- ↳ Kryptografické protokoly
- ↳ Úvod do teorie grup
- ↳ Právní aspekty zabezpečení dat
- ↳ Komutativní okruhy
- Fyzika ZS
- ↳ Výuka ZS 1. ročník
- ↳ OFY067 Fyzika v experimentech I
- ↳ MAF027 Lineární algebra I
- ↳ OFY021 Fyzika I (mechanika a molekulová fyzika)
- ↳ OFY056 Programování pro fyziky
- ↳ MAF033 Matematická analýza I
- Oborový mix aktuální
- ↳ Anglický jazyk
- ↳ Tělesná výchova
- ↳ Granty GAUK
- Odkazy
- ↳ Wiki
- ↳ SKAS
- ↳ Spolek Matfyzák
- Matematika Archiv
- ↳ Výuka LS 2006/2007 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Výuka LS 2006/2007 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Angličtina
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 2006/2007 1. ročník
- ↳ Volitelné předměty
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- Zrušené předměty
- ↳ SWI087 Principy počítačů
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG029 Programování v C++
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG032 Objektově orientované programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI097 Základy operačních systémů
- ↳ NDBI003 Organizace a zpracování dat II
- Roztřídit (resty)
- ↳ Výuka ZS 2005/06 2. ročník
- ↳ Předměty informační bezpečnosti
- ↳ Předměty finanční matematiky
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Analýza/kalkulus
- ↳ Matematika obecně
- ↳ Výuka LS 2005/06 2.ročník
- ↳ Základy matematického modelování
- ↳ Finanční management
- ↳ Úvod do optimalizace
- ↳ Numerika
- ↳ Kalkulus
- ↳ Angličtina
- ↳ Diferenciální geometrie
- ↳ Pravděpodobnost a statistika
- ↳ Teorie míry a integrálu II
- ↳ Algebra II
- ↳ Analýza 2b