Implementace algoritmu problému batohu

[kandri]

Ahoj, potrebujem naprogramovat algoritmus na riesenie problemu batohu, a chcel by som sa spytat na dve veci. Prva vec, aky datovy typ vyzera byt najvhodnejsi na ukladanie jednotlivych poloziek (programujem v C++)? Druha otazka, robim zatial len brute force metodu, mozno sa budem za to pri citani odpovedi hanbit (myslim si, ze to bude primitivne), ale teraz nejak neviem prist na nejake rozumne riesenie, ako prejst vsetky mozne kombinacie jednotlivych poloziek. Problem mam s tym, ze ak mam napr 5 poloziek, tak potrebujem skontrolovat aj kombinacie po dvoch, ale aj po 3, 4 atd, a to nejak neviem vymysliet. Vedel by mi niekto poradit? Dakujem.

[Reklama]

[hawran diskuse]

Ahoj, potrebujem naprogramovat algoritmus na riesenie problemu batohu, a chcel by som sa spytat na dve veci. Prva vec, aky datovy typ vyzera byt najvhodnejsi na ukladanie jednotlivych poloziek (programujem v C++)? Druha otazka, robim zatial len brute force metodu, mozno sa budem za to pri citani odpovedi hanbit (myslim si, ze to bude primitivne), ale teraz nejak neviem prist na nejake rozumne riesenie, ako prejst vsetky mozne kombinacie jednotlivych poloziek. Problem mam s tym, ze ak mam napr 5 poloziek, tak potrebujem skontrolovat aj kombinacie po dvoch, ale aj po 3, 4 atd, a to nejak neviem vymysliet. Vedel by mi niekto poradit? Dakujem.

Klidně naprogramuj nějaké tupé (brutal force?), ale funkční řešení.
Optimalizuje se až potom.

[kandri]

No momentalne som zaseknuty na tom, ze neviem ako rozumne vymysliet, aby mi to spravilo vsetky mozne kombinacie.  Keby som mal staticky pocet prvkov, tak okej, nahadzem tam 4 vnorene fory a idem, ale mozem tam mat tych poloziek aj 10. Takisto nechcem vsetky kombinacie so vsetkymi prvkami, ale aj kombinacie len po 2,3,4 atd. S tymto by som potreboval nejak nakopnut. Dakujem velmi pekne.

[Kit]

Zkus se podívat, jak to řeší jiní:
https://www.algoritmy.net/article/5521/Batoh

[jk]

algoritmy k batohu najdes v knize Knapsack Problems: Algorithms and Computer Implementations od Martello, Toth. Chapter2.pdf pokryva nekolik algoritmu/schemat pro 0-1 knapsack (predpokladam, ze resis ten)

generovanim instanci se zabyva David Pisinger: http://www.diku.dk/~pisinger/codes.html

na generovani podmnozin (pri bruteforce reseni potrebujes otestovat vsechny podmnoziny) si proste vygugli "generating all subsets". dela se to vetsinou pres indikatorovou funkci (v kodu pomoci bitwise operaci vygenerujes vsechny retezce 0 a 1 o dane delce)

[Reklama]

[Jenda]

Prva vec, aky datovy typ vyzera byt najvhodnejsi na ukladanie jednotlivych poloziek (programujem v C++)?

To přece záleží na tom, jaké ty položky mají ceny/hmotnosti. Malá celá čísla? Velká celá čísla? Lze vydělit společným jmenovatelem? Jsou to floaty a očekává se řešení v rámci floatové přesnosti?

Druha otazka, robim zatial len brute force metodu, mozno sa budem za to pri citani odpovedi hanbit (myslim si, ze to bude primitivne), ale teraz nejak neviem prist na nejake rozumne riesenie, ako prejst vsetky mozne kombinacie jednotlivych poloziek.

Ono totiž obecné rozumné řešení neexistuje (nebo o něm alespoň nikdo neví), batoh je NP-complete. Ale pokud vstup splňuje nějaké podmínky, například jsou čísla po vydělení společným jmenovatelem „malá“, lze použít pseudopolynomiální algoritmus. A pokud nepožaduješ přesné řešení, lze použít nějaký z aproximačních algoritmů a heuristik. Všechno toto se píše na Wikipedii.

A pokud je to ten domácí úkol, co se zadává v prváku na matfyzu, tak tam se očekává právě ten pseudopolynomiální algoritmus

Keby som mal staticky pocet prvkov, tak okej, nahadzem tam 4 vnorene fory a idem, ale mozem tam mat tych poloziek aj 10.

Druhý výsledek Googlu na "knapsack problem bruteforce" používá rekurzi ve stylu

Kód: [Vybrat]

function solve(n, currentWeight, currentValue) {
    # don't pack this item
    solve(n-1, currentWeight, currentValue)
    # pack this item
    solve(n-1, currentWeight + w[n], currentValue + v[n])
}

Přijde mi to jako docela rozumný začátek. S trochou štěstí by to mohlo být i rychlejší než indikátorová funkce - na tu si zase dokážu představit nějaký šílený SSE/AVX udělátor, ale to v první iteraci asi fakt psát nechceš.

[mt]

Problém batohu se před lety řešil na FELu v předmětu PAA, takže na webu lze určitě dohledat desítky řešení i s českým popisem. Např:

http://tumic.wz.cz/fel/online/36PAA/1/
http://tumic.wz.cz/fel/online/36PAA/3/
http://tumic.wz.cz/fel/online/36PAA/5/

[gll]

Ahoj, potrebujem naprogramovat algoritmus na riesenie problemu batohu, a chcel by som sa spytat na dve veci. Prva vec, aky datovy typ vyzera byt najvhodnejsi na ukladanie jednotlivych poloziek (programujem v C++)? Druha otazka, robim zatial len brute force metodu, mozno sa budem za to pri citani odpovedi hanbit (myslim si, ze to bude primitivne), ale teraz nejak neviem prist na nejake rozumne riesenie, ako prejst vsetky mozne kombinacie jednotlivych poloziek. Problem mam s tym, ze ak mam napr 5 poloziek, tak potrebujem skontrolovat aj kombinacie po dvoch, ale aj po 3, 4 atd, a to nejak neviem vymysliet. Vedel by mi niekto poradit? Dakujem.

Klidně naprogramuj nějaké tupé (brutal force?), ale funkční řešení.
Optimalizuje se až potom.

V tomhle pripade neni ta optimalizace uplne intuitivni. Brute force reseni vas nasmeruje spatnym smerem. Souhlasim, ze vetsinou byva dobra strategie napsat nejjednodussi korektni reseni a proti nemu testovat spravnost vysledku. U neceho takto znameho to ani neni treba, staci zagooglit.

[JardaP .]

Tak snad zalezi take na to, kolik a jakych batohu chci resit. Pokud nechci resit tisice batohu o objemu v tunach, do kterych chci skladat nanogramove polozky, ale treba jen jeden batoh o normalnim objemu a do nej dat par polozek vahy predmetu denni potreby, tak je uplne jedno, jestli to je nebo neni optimalizovane.