Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 10. 08. 2011 19:02
Batoh
Zdravím, řeším jednu úlohu do Algoritmizace, u které tuším, že povede na rekurzi, neumím ji však správně použít.
Máme předměty s různými celočíselnými váhami (váhy známe) a ty chceme do batohu (víme jeho nosnost) dát tak, aby byl celý přesně naplněný a předmětů v něm bylo co nejméně. Můžeme předpokládat, že řešení existuje.
Takže například pro hodnoty:
A: 13 kg
B: 10 kg
C: 8 kg
D: 2 kg
a nosnost batohu 24 kg
By jedním řešením bylo naložit tři předměty typu C.
Napadlo mne, že bych mohla do batohu postupně "nakládat" předměty od velkých po menších, ale tak by to nešlo. Na příkladu výše by to totiž naložilo nejprve předmět A, poté by se tam vešel předmět B a poté by zbyl jeden kilogram nevyužitý...
Za každou radu předem díky.
Offline
#2 10. 08. 2011 20:25 — Editoval quardiola (10. 08. 2011 20:26)
Re: Batoh
Offline
#3 10. 08. 2011 20:27
#5 10. 08. 2011 22:09
- check_drummer
- Příspěvky: 5511
- Reputace: 106
Re: Batoh
↑ Katka91:
Jestli je NP úplná pak ano. Resp. ne úplně všech, ale takového počtu, aby to trvalo dost dlouho. :-)
"Máte úhel beta." "No to nemám."
Offline
#6 10. 08. 2011 22:52
Re: Batoh
Problém batohu je jinak řešen třeba zde: http://www.algoritmy.net/article/5521/Batoh
Sice tam není totožný problém, ale velice podobný
To zadání mi docela připomíná druhou úlohu tady http://mo.mff.cuni.cz/p/61/zadani-1.html
Offline
#7 11. 08. 2011 12:24
Re: Batoh
↑ check_drummer: Myslím ale, že to bude muset mít lepší řešení, potřebuji to na zápočet.
Offline
#8 11. 08. 2011 12:52
Re: Batoh
↑ Katka91:no lepsi je to aspon nejak udelat a pak popripade to nejak doladit zrychlit
Offline
#9 21. 08. 2011 18:49
- OiBobik
- Moderátor
- Místo: Brno/Praha
- Příspěvky: 1013
- Škola: MFF UK Mat. struktury
- Pozice: student
- Reputace: 82
Re: Batoh
↑ Katka91:
Pokud máme nosnost batohu nějak rozumně omezenou (např. 10000), pak půjde o úlohu dynamického programování. Základem bude pole o rozměru, jako je maximální nosnost. Program pak bude pracovat tak, že bude do pole zaznamenávat, na jaké hodnoty celkové hmotnosti batohu lze předměty nakombinovat (a případně si pamatovat, které z předmětů kolikrát vzal, aby takové hmotností konfigurace dosáhl)(pole tedy bude např booleanové, hodnota true na n-té pozici bude znamenat, že lze předměty nakombinovat na celkovou hmotnost n kg - pokud nám jde o konkrétní podobu konfigurace, vytvoříme místo toho pole integerové a při nalezení konfigurace "n kg" si uložíme hmotnost bez posledního přidaného předmětu, čímž po nalezení nejlepší konfigurace snadno zrekonstruujeme konkrétní kombinaci předmětů, které je potřeba pro onu konfiguraci do batohu vložit; jde-li nám navíc o to, dosáhnout optimálního zaplnění co nejméně předměty, pak sledujeme navíc i údaj "kolik předmětů musí v batohu pro danou hmotnost batohu být" a pokud najdeme dále v průbehu programu lepší, pak tento údaj snižujeme a s ním přepisujeme i poslední přidaný předmět).
"The first rule of Tautology Club is the first rule of Tautology Club." [xkcd]
Offline