Wiki » Zgodovina » Verzija 1
Jakob Beber, 22.05.2025 21:13
| 1 | 1 | Jakob Beber | h1. Predstavitev raziskovalne naloge Pokrivanje Košev |
|---|---|---|---|
| 2 | 1 | Jakob Beber | |
| 3 | 1 | Jakob Beber | Problem pokrivanja košev je prisoten v raznolikih poslovanjih in industrijah. Od preprostih problemov, kot je pakiranje hrane v emabalažo tako, da vsaka embalaža vsebuje vsaj določeno neto težo, do kompleksnih problemov, kot je porazdelitev dela med tovarne, da le te delujejo pri minimalno izvedljivi ravni. Učinkovita rešitev problema pokrivanja košev tako optimizira delovanje podjetji. Pri problemu pokrivanja košev imamo podano množico predmetov različnih velikosti z intervala (0,1). Predmete zlagamo v koše, kjer koš postane pokrit, če je velikost predmetov v košu vsaj 1. Problem, ki ga rešujemo, je razporeditev predmetov v koše tako, da je število pokritih košev čim večje. Assmann et al. so dokazali, da je problem pokrivanja košev NP-težek [1]. Zgornji problem ima sprotno enačico (online version), kjer predmeti prihajajo eden za drugim. Vsak dobljen predmet moramo odložiti v koš, preden pride naslednji predmet. |
| 4 | 1 | Jakob Beber | |
| 5 | 1 | Jakob Beber | |
| 6 | 1 | Jakob Beber | h2. Literatura: |
| 7 | 1 | Jakob Beber | |
| 8 | 1 | Jakob Beber | [1] Susan F Assmann, David S. Johnson, Daniel J. Kleitman, and JY-T Leung. |
| 9 | 1 | Jakob Beber | On a dual version of the one-dimensional bin packing problem. Journal of |
| 10 | 1 | Jakob Beber | algorithms, 5(4):502–525, 1984. |