Avatar
Merry
Člen
Avatar
Merry:

Mam zadaný ukol, který delam asi 2 dny a nejsem schopný to nejak spackat. Tak dkyby nahodou si stim někdo vedel rady. Mam cas jenom do pulnoci pak to musi odevzdat. Diky.

Implementujte algoritmus pro nalezení optimálního řešení Set-Cover problému. Předpokládejte, že universum je podmnožinou přirozených čísel. Vstupní instanci program načte z textového souboru. Každý z řádků tohoto souboru obsahuje mezerou oddělená čísla, a odpovídá jednomu prvku ze systému podmnožin universa. Samotné universum je pak tvořeno sjednocením těchto podmnožin.

Odpovědět 16.12.2012 18:35
Jste dobří jen v tom, co vás baví.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Merry
David Čápka:

Nějaké lidštější zadání by nebylo?

Nahoru Odpovědět 16.12.2012 18:49
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Merry
Člen
Avatar
Merry:

Taky si rikam, proste vygenerovat podmnoziny nejake mnoziny, a poté zjistit nejmenši pokryti no, prsote mnozinu ktera pokryva celou mnozinu(což byal ta vstupni)

Nahoru Odpovědět 16.12.2012 19:21
Jste dobří jen v tom, co vás baví.
Avatar
Luboš Běhounek (Satik):

Jestli to chapu dobre:

  • Mas soubor, ve kterem jsou radky a na kazdem radku jsou v textove forme cisla oddelena mezerou
  • Mas zjistit vsechny cisla, ktery se v souboru vyskytujou

je to tak?

Nahoru Odpovědět 16.12.2012 19:25
:)
Avatar
Merry
Člen
Avatar
Merry:

No zjistit, hlaven pak zjistit to opkryti mnoziny. nejmenší. Jinak Set-Cover je progr. problém viz. http://en.wikipedia.org/…over_problem

Nahoru Odpovědět 16.12.2012 19:28
Jste dobří jen v tom, co vás baví.
Avatar
Merry
Člen
Avatar
Merry:

Jinak tady je pdf kde je o tom napsano i s pseudokodem, ale moje hlava to prsote porad nebere. http://leteckaposta.cz/597785411
je to asi ve stredu, je tam nadpis Set-Cover

Editováno 16.12.2012 19:34
Nahoru Odpovědět 16.12.2012 19:33
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Mělo by to být podle tohoto:
http://en.wikipedia.org/…over_problem

Na vstupu je n podmnožin, jejichž sjednocením je universum. Naším úkolem je vyházet co nejvíc podmnožin tak, aby sjednocením zbylých podmnožin bylo stále umiversum.

Nahoru Odpovědět 16.12.2012 19:38
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Kit
Redaktor
Avatar
Odpovídá na David Čápka
Kit:

Mělo by to být podle tohoto:
http://en.wikipedia.org/…over_problem

Na vstupu je n podmnožin, jejichž sjednocením je universum. Naším úkolem je vyházet co nejvíc podmnožin tak, aby sjednocením zbylých podmnožin bylo stále umiversum.

Nahoru Odpovědět 16.12.2012 19:38
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Merry
Člen
Avatar
Merry:

Ano přesně tak ;-). Je to ukol do Algoritmické matematky, meli sme toho vic. Jediny tohle fakt nevim jak udelat. Tak kdyby ste mohli helpnout. Na jazyce nezalezi (Java, C#), hlavně ne najkej lisp, scheme atd :D

Nahoru Odpovědět 16.12.2012 19:41
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Merry
Kit:

Podle toho PDF bys na to měl jít backtrackingem. Odebrat jednu podmnožinu a ověřit si, zda je stále podmínka splněna. Pokud ano, odebrat další. Pokud ne, vrátit se o krok zpět a odebrat jinou. To vše nejlépe rekurzí.

Úspěšný stav si ulož, ale jen pokud je počet podmnožin menší, než předchozí uložený stav.

Nahoru Odpovědět 16.12.2012 19:53
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Merry
Člen
Avatar
Merry:

Backtracking neni nutný, mužeme pouzit i Greedy metodu. Tohle chápu, ale nedal sem to dohromady za celej den. Sem pišu prtoože sem zoufalej už

Nahoru Odpovědět 16.12.2012 20:00
Jste dobří jen v tom, co vás baví.
Avatar
Merry
Člen
Avatar
Merry:

Navíc na to mam necely 4 hodiny už. Mam to posalt do 12ti hodin. Kite nepořešil bys to? Je mi to blbý ale bud tohle nebo přisti rok ten predmet

Nahoru Odpovědět 16.12.2012 20:10
Jste dobří jen v tom, co vás baví.
Avatar
Kit
Redaktor
Avatar
Odpovídá na Merry
Kit:

Jenže já za tebe nemůžu řešit tvé úkoly. Zkusil jsem se podívat na tu problematiku, protože mě to zaujalo, ale dělat se mi to nechce.

Ještě mě napadlo jednodušší řešení u toho backtrackingu. Jako u batohu. Prostě pořád přidávat, dokud není splněna podmínka universa. Poznamenat řešení, pokud je kratší. Pak couvnout a pokračovat dalšími větvemi. Pokud jsou větve vyčerpány, opět couvnout.

S rekurzí bys to měl mít za chvilku hotové.

Nahoru Odpovědět 16.12.2012 20:26
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Luboš Běhounek (Satik):

Tady jsem se o to pokusil, snad jsem to pochopil dobře. Není to moc otestovaný, nejsou ošetřený chyby...
http://satik.eu/…setcover.zip

Nahoru Odpovědět 16.12.2012 20:29
:)
Avatar
Merry
Člen
Avatar
Merry:

To já pravě taky si myslel. Ale nevědel sem si pak rady. Ok no, Kdyby nahodou se někomu chtělo tak do 12ti. Kdybych nebyl tak zoufalej tak sem nepiši. Ale jde mi o kredity ve skole no.

Nahoru Odpovědět 16.12.2012 20:38
Jste dobří jen v tom, co vás baví.
Avatar
Odpovídá na Merry
Luboš Běhounek (Satik):

Viz můj předchozí příspěvek, je to přes rekurzi.

Btw o kredity jde tobe, ne nám, tak se tu kvůli tvému úkolu nikdo nepřetrhne, jen teď jsi měl štěstí, že jsem měl čas a chuť si tohle vyzkoušet napsat ;)

Editováno 16.12.2012 20:43
Nahoru Odpovědět 16.12.2012 20:39
:)
Avatar
Merry
Člen
Avatar
Merry:

To jo :D Takovou hlavu jak vy bych chtěl mět :D Každopadně moc děkuju a omlouvam se za to že sem pišu aby ste mi něco udělali. Vím jaky toje a jak to vypadá ale byl sem zoufalej. Zachranil si mi 5 kreditu :) Díky moc :-)

Nahoru Odpovědět 16.12.2012 20:42
Jste dobří jen v tom, co vás baví.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Luboš Běhounek (Satik)
David Čápka:

Týjo, to je rychlost :) Nechceš to sem přidat do ukázkových programů? Práce s množinami se někomu určitě ještě hodí.

Nahoru Odpovědět 16.12.2012 21:07
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 19 zpráv z 19.