Matematické Fórum

Akcope · 10. 05. 2013 17:51

Ahoj, jak bych měl obecněji řešit problém batohu?

Máme např. batoh, který unese 5 kg. Vstupní množina obsahuje předměty s hmotnostmi 4, 3 a 2 kg. A máme najít optimální řešení.

Když vezmeme vždy největší možný prvek - v tomto případě 4kg, nedospějeme k optimálnímu řešení (což je evidentně 3 a 2 kg).

Jak získat obecný algoritmus, kterým vždy dostaneme optimální řešení? Předem díky za odpověď.

check_drummer · 10. 05. 2013 19:52

↑ Akcope:
Ahoj, není to náhodou NP-úplný problém? Obecný algoritmus může být "výzkoušet všechny možnosti" - s případnými drobnými vylepšeními - jako: není nutné přidávat, pokud již je batoh přeplněn, apod.

Stýv · 10. 05. 2013 20:43

viz http://kam.mff.cuni.cz/~perm/programova … slidy7.pdf

↑ check_drummer: pokud jsou všechny údaje celočíselný, tak to NP-úplný není

Akcope · 10. 05. 2013 22:41

↑ Stýv:
Díky :)

check_drummer

↑ Stýv:
Ahoj, to je známý trik. :-) Jedná se o tzv. pseudopolynomiální algoritmus (aspoň tuším, že se mu tak říká), který však je NP: na vstupu úlohy je totiž číslo m, které lze tedy vyjádřit pomocí log(m) "bitů". Tedy vstup má velikost log(m) - a nikoli m (plus hmotnosti předmětů a jejich ceny, to ponechme stranou) - ovšem doba běhu algoritmu má velikost m (opět krát výraz závislý na počtu předmětů, opět ponechme stranou), tedy je exponenciální vzhledem k velikosti vstupu (log(m)).

Ještě přidávám odkaz.

Matematické Fórum

#1 10. 05. 2013 17:51

Hladový algoritmus (Zavazadlový problém)

#2 10. 05. 2013 19:52

Re: Hladový algoritmus (Zavazadlový problém)

#3 10. 05. 2013 20:43

Re: Hladový algoritmus (Zavazadlový problém)

#4 10. 05. 2013 22:41

Re: Hladový algoritmus (Zavazadlový problém)

#5 11. 05. 2013 20:23 — Editoval check_drummer (11. 05. 2013 20:29)

Re: Hladový algoritmus (Zavazadlový problém)

Zápatí