- Redmi Note 9 - azt nyújtja, amit ígér
- Milyen GPS-t vegyek?
- Felújított okostelefonokat kínál a Rejoy
- Poco X6 Pro - ötös alá
- Samsung Galaxy S23 és S23+ - ami belül van, az számít igazán
- Android szakmai topik
- MG4 menetpróba
- Garmin Forerunner 165 - alapozó edzés
- Motorola Moto G24 Power - hol van az erő?
- Fotók, videók mobillal
Hirdetés
-
Lenovo Essential Wireless Combo
lo Lehet-e egy billentyűzet karcsú, elegáns és különleges? A Lenovo bebizonyította, hogy igen, de bosszantó is :)
-
Robotkart irányított a majom a kínai Neuralink agyi chipjével
it A mindezt lehetővé tévő Neucybert a Neuralink kínai riválisa, a Beijing Xinzhida Neurotechnology fejlesztette ki.
-
Premier előzetesen a Wrath: Aeon of Ruin konzolos változatai
gp A PC-s változat után a minap PlayStationre, Xbox-ra és Switch-re is elérhető lett a program.
-
Mobilarena
Új hozzászólás Aktív témák
-
amargo
addikt
válasz peterszky #3032 üzenetére
Jajjj megvakulok, amúgy szerintem emészthetőek a stuktogrammok, de előtte a levezetések...
Igaz ezek nem a teljes stuktogrammok, azokból könyebb megérteni a lényegét, mert ez így“The workdays are long and the weekend is short? Make a turn! Bike every day, bike to work too!”
-
peterszky
őstag
válasz peterszky #6432 üzenetére
Elnézést, nem voltam pontos, nem csak az összérték a lényeg, hanem hogy kinyerjünk egy olyan listát, ami megadja, hogy az egyes első listabeli elemeknek az összegét melyik második listabeli elemek adják ki (és a második listából minden elemet csak egyszer lehet felhasználni), tehát egy jó megoldás pl.:
100 - 50, 50
200 - 10, 20, 30, 30, 30, 40, 40
300 - 20, 30, 50, 50, 50, 100
Marad: 10, 20, 20, 100, 100, 200, 200[ Szerkesztve ]
What else you gonna do on a Saturday?
-
sztanozs
veterán
válasz peterszky #6433 üzenetére
Egy megoldást kell találni, vagy az összes lehetségest?
Egy megoldásra le kell programozni, hogy hozza létre szép sorban az összes (olyan elem, ami a célnál kisebb) elem kombinációját 1-től n darabig és az első jó megoldásnál kilépni. Az összesre ugyanez a feladat, csak szépen ki kell írni (el kell tárolni) az összes jó kombinációt...
Megvalósítást tekintve a rekurzív listafeldolgozás jut az eszembe:
az aktuális összeghez hozzáadja a következő listaelemet és a lista maradák elemeivel meghívja saját magát... (Növekvő) sorrendbe rakva még célszerű odafigyelni az aktuális listaösszegre és visszalépni egyet a rekurzióban, ha az összeg meghaladja a célt (gyorsítható a futás, ha nem számol ki minden lehetséges kombinációt, csak ami kisebb, vagy egyenlő, mint a cél).Mondjuk szerintem ez a "bruteforce" megoldás... Kíváncsi vagyok tud-e valaki kevésbé BF-ot. Bár elsőre belegondolva, ha csökkenő sorrendben van a lista, akkor a (majdnem) triviális megoldásokat hozza:
100 - 100
200 - 200
300 - 200 + 100[ Szerkesztve ]
JOGI NYILATKOZAT: A bejegyzéseim és hozzászólásaim a személyes véleményemet tükrözik; ezek nem tekinthetők a munkáltatóm hivatalos állásfoglalásának...
-
modder
aktív tag
válasz peterszky #6435 üzenetére
Hasonlít a hátizsák problémára:
legyenek a számok súlyok. A hátizsákok az 1. listabeli elemek, maximális súly kapacitásuk pedig a szám.
A téglák a 2. listabeli elemek, súlyuk szintén maga a szám, értékük pedig legyen annál nagyobb, minél nagyobb a szám: tehát lehet maga a szám az érték is. Ez azért jó, mert ha úgy pakolsz egy hátizsákba, hogy nagyobb téglákat használsz, azzal kevesebbet is egyben, így nagyobb lesz a valószínűsége annak, hogy a kisebb értékekből a többi zsákot meg tudod tömni: mert több kisebb értékből több kombinációt tudsz összehozni.A probléma az, hogy amíg egy zsákos problémára van optimális algoritmus, addig a több zsák egy NP-teljes probléma, amire nincsen egzakt algoritmus. Elfogadható időben csak egy közelítőleg jó megoldást tudsz találni.
A probléma inkább erre hasonlít: http://en.wikipedia.org/wiki/Bin_packing_problemOtt van is két algoritmus.
Jó lenne tudni, hogy az 1. listabeli elemeket MINDIG ki lehet-e rakni teljesen a 2. listabeli elemekből, mert ha nem, akkor be kell vezetni egy mércét, ami értékeli a megoldást: Minél több 1. listabeli elemet tettünk ki; Minél több számot használtunk fel teljesen a 2. listából; Az 1. listabeli teljesen kirakott elemek összege maximális;
Nézd meg a fenti linket.
-
válasz peterszky #8947 üzenetére
nem tudom, hogy mit értesz brute force megoldás alatt, de a brute force azt jelenti, hogy agyatlanul végigpróbálgatod az összes lehetséges verziót és kiválasztod a végeredményt. tehát az mindig megtalálja a megoldást, ha van.
a mai világban egy 56 elemű listának én brute force módszerrel állnék neki, backtrack egy intelligensebb változatával próbálkoznék. memória nem kell neki sok, a processzorodat agyonüti, de ez engem nem izgatna
Egy átlagos héten négy hétfő és egy péntek van (C) Diabolis
-
inf3rno
nagyúr
válasz peterszky #8947 üzenetére
Nem hiszem, hogy ez lehetséges, ha ekkora számokról van szó, és random a dolog. Max közelítőleg lehet megtalálni, hogy mi a jó db szám.
Algoritmust nem tudok javasolni, mert ahhoz nem értek. Talán sorba kellene rendezni, és az összeg és az irányszám különbségénél kisebb elemek összeadásával próbálkozni. Jelen esetben ez 591511, szóval mind a 27 elem részt vesz a játékban. Én sem hiszem, hogy erre ne lenne elég a brute force, nem százezer elemes dolgokról van szó. Még excel is 1-2 sec alatt kiszámolta nekem a megoldójával, mondjuk az ránézésre monte carlo-val megy, mert könnyen beragad egy értékre, ami nem is a legoptimálisabb. Esetleg nyálazz át egy algoritmusos könyvet, ha az optimális megoldás kellene.
Buliban hasznos! =]
-
axioma
veterán
válasz peterszky #8947 üzenetére
Azt azert nem artana tisztazni, hogy a feladatra milyen korlatok vannak: csak pozitiv egeszek lesznek-e (felteszem igen), ismetles lehet-e (mivel talaltam egyformat, gondolom nem), mi a korlatja a darabszamnak, ilyesmi... azert a hatvanyhalmaz eleg durva tudna lenni. Ha ez nem valami iskolai feladat, akkor az inputok honnan vannak, lehet-e valami "szoft" osszefuggest kiszedni belole?
Es a brute force-nal mi az az 1%? Az nem tud nem bejonni. Kifejtened? -
sztanozs
veterán
válasz peterszky #8956 üzenetére
szvsz ha van megoldás, sima backtack-kel megoldható: a legmagasabbtól indulva, összeadva, amíg nagyobb vagy egyenlő nem lkesz, aztán ha nagyobb, akkor backtack. Ha a backtack után (vagy akár az első lépésben) összes elérhető szám összege kisebb, mint kívánt, akkor nincs megoldás.
Amúgy csak pontos megoldás jöhet szóba (range nem)?JOGI NYILATKOZAT: A bejegyzéseim és hozzászólásaim a személyes véleményemet tükrözik; ezek nem tekinthetők a munkáltatóm hivatalos állásfoglalásának...
-
axioma
veterán
válasz peterszky #8956 üzenetére
Ismetlesnel arra gondoltam, hogy ugyanaz az index 2x lehet-e (egy szam - ha csak 1x van is - felhasznalhato-e ketszer), de gondolom akkor nem.
Ja, hogy az 1%-ot ugy erted, hogy akkor nem jon ki, amikor a (melysegi) kereses nem talalja meg az elejen... azaz nem is nem jon ki, hanem nem varjatok ki.
Ha ezek penzosszegek, akkor gondolom lehet felso korlat a szummara, mondjuk 10M. Teged pedig legfeljebb a 10M alatti osszes szam _egyfele_ osszeallitasa erdekel. DE: az egyes ertekekhez me'g erre sincs szukseged. Eleg az utolso elemet tudni, ami kellett ahhoz, hogy o osszealljon. (Az egyikben.)
Szoval reszemrol a kovetkezo algot probalnam be:
map int->int
indulaskor 0->0
csokkeno sorrendben a szamok, mindegyiknel a map minden elemehez hozzaadod, es ha kisebb a celszamnal es nincs me'g benne, akkor beteszed az uj szamot rendelve hozza.
amikor megkapod a celszamot pont, akkor abort, es visszakeresed: a map-ben milyen szamot irtal melle, kivonod a celszamobol azt, es keresed a map-ben a maradekot. Ismetled amig a 0->0-hoz nem jutsz. Voila, megvan a keresett halmaz.
Ez igy ordomax^2*darabszamordo max^2*ln(max)*darabszam (a map koltsegigenye miatt) komplexitas idoben, es ordo max tarhelyben. Azt neked kell tudnod, hogy ez belefer-e.
Ilyesfajta megoldasra gondoltal?[ Szerkesztve ]
-
sztanozs
veterán
válasz peterszky #8956 üzenetére
Nekem ez jött ki backtrack-kel:
119709
84657
68233
50364
12047
3650
2136
1553
1470
891A megoldást (excel vba) majd feltolom valahová.
JOGI NYILATKOZAT: A bejegyzéseim és hozzászólásaim a személyes véleményemet tükrözik; ezek nem tekinthetők a munkáltatóm hivatalos állásfoglalásának...
-
axioma
veterán
válasz peterszky #8971 üzenetére
Upsz, ez az en megoldasomban se volt benne... sot, ellenorzessel se megoldhato, hanem tobb info kell 1 szam elereserol (ha kulonbozo darabszamu). Szoval jelen esetben a kivant darabszam a tarolasi igenynel bejon szorzonak. Szoval int->int[db+1] kell, es okos masolas...
-
sztanozs
veterán
válasz peterszky #8971 üzenetére
Elsőre azt hittem, hogyran végigfuttatom, de aztán rájöttem, nem ártana kiszámolni mennyi lehetséges állapotból kellene kiválasztani a jót:
PERM(56, 27) = 8*10^43Asszem leállítom a számolást.
JOGI NYILATKOZAT: A bejegyzéseim és hozzászólásaim a személyes véleményemet tükrözik; ezek nem tekinthetők a munkáltatóm hivatalos állásfoglalásának...
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
- AMD GPU-k jövője - amit tudni vélünk
- Intel Core i5 / i7 / i9 "Alder Lake-Raptor Lake/Refresh" (LGA1700)
- Otthonfelújítási program (2024.)
- Milyen belső merevlemezt vegyek?
- Kerékpárosok, bringások ide!
- Kertészet, mezőgazdaság topik
- Házi barkács, gányolás, tákolás, megdöbbentő gépek!
- A fociról könnyedén, egy baráti társaságban
- Escape from Tarkov
- Borotva, szakállnyíró, szakállvágó topic
- További aktív témák...