- Samsung Galaxy S23 és S23+ - ami belül van, az számít igazán
- Telekom mobilszolgáltatások
- Samsung Galaxy S24 Ultra - ha működik, ne változtass!
- Android alkalmazások - szoftver kibeszélő topik
- Yettel topik
- Garmin Forerunner 165 - alapozó edzés
- iPhone topik
- Samsung Galaxy A54 - türelemjáték
- A Watch7-tel debütálhat a Samsung vércukormérője
- Huawei Watch GT 4 - kerek karék
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 :)
-
A Video AI lehet a One UI 6.1.1 ütőkártyája
ma Vagy hogy fogja a mesterséges intelligencia manipulálni a mozgóképeket?
-
Rossz üzlet az EV-kölcsönzés
it Küszködik az EV-kölcsönzés miatt a Hertz Global, még több EV-t adnak el.
-
Mobilarena
Új hozzászólás Aktív témák
-
peterszky
őstag
Most lehet, hogy lincshangulat fog kialakulni , de itt is van egy szép kis backtrack:
[Backtrack]
Nem mondanám, hogy könnyen emészthető (nekem sem sikerült tökéletesen )What else you gonna do on a Saturday?
-
peterszky
őstag
Algoritmus ügyben lenne egy kérdésem:
Van két listám. Az egyik n db számot tartalmaz, pl.:
100, 200, 300A másik m db számot tartalmaz rendezetten, pl.:
10, 10, 20, 20, 20, 20, 30, 30, 30, 30, 40, 40, 50, 50, 50, 50, 50, 100, 100, 100, 200, 200A feladat egy olyan megoldást találni, amely a második listából vesz elemeket és azok összegéből kiadja az első listában található összértéket (lehet 0, 1, >1 megoldás, mindegy melyik lesz meg). A kérdés az, hogy a bruteforceon kívül van-e erre valami elegánsabb megoldás?
What else you gonna do on a Saturday?
-
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?
-
peterszky
őstag
válasz sztanozs #6434 üzenetére
Köszi! Egy megoldás elég, nem kell az összes. Amúgy most találtam rá a "Knapsack problem"-re, elsőre úgy tűnik, hogy erre érdemes elindulni.
[ Szerkesztve ]
What else you gonna do on a Saturday?
-
peterszky
őstag
Egyelőre úgy tűnik, hogy elég az egy hátizsák problémát megoldani, ez kész is van (0-1 knapsack, dinamikus programozás megközelítéssel). Viszont itt felötlött bennem, hogy a munkatábla férőhelye igen gyorsan elfogadhatatlan méretűre nőhet, mivel a "kirakandó" összeg lehet akár milliós nagyságrendű is (és a tábla oszlopai ugye 0 -> kapacitásig tartanak).
What else you gonna do on a Saturday?
-
peterszky
őstag
Van egy valós életbeli problémám, a lényeg, hogy vannak értékek, emellett egy darabszám és egy összeg. A bruteforce megoldás 99%-ban jól működik, de ott az az 1%, ami bármikor bejöhet és mint tudjuk, ez be is jön.
A lényeg, hogy az alábbi listában a végén látható darabszámban vegyünk ki értékeket úgy, hogy a végén látható összeg kijöjjön.
Knapsack vagy ennek egy változata volt talán az, amit nézegettem, de egyelőre nem tudom eldönteni, hogy melyik megoldásnak kellene nekiállni, a dinamikus programozás változata ilyen értékeknél, ha jól értelmeztem, akkor elég halál memória szempontból.
Esetleg valakinek van javaslata, merre lenne érdemes nézelődni még?
NDX: 0 OSSZEG: 119709
NDX: 1 OSSZEG: 84657
NDX: 2 OSSZEG: 68233
NDX: 3 OSSZEG: 50364
NDX: 4 OSSZEG: 40664
NDX: 5 OSSZEG: 37626
NDX: 6 OSSZEG: 32079
NDX: 7 OSSZEG: 31902
NDX: 8 OSSZEG: 28440
NDX: 9 OSSZEG: 26180
NDX: 10 OSSZEG: 20632
NDX: 11 OSSZEG: 20535
NDX: 12 OSSZEG: 18548
NDX: 13 OSSZEG: 17824
NDX: 14 OSSZEG: 16424
NDX: 15 OSSZEG: 16406
NDX: 16 OSSZEG: 15864
NDX: 17 OSSZEG: 14909
NDX: 18 OSSZEG: 14907
NDX: 19 OSSZEG: 14131
NDX: 20 OSSZEG: 13956
NDX: 21 OSSZEG: 12374
NDX: 22 OSSZEG: 12047
NDX: 23 OSSZEG: 11621
NDX: 24 OSSZEG: 11269
NDX: 25 OSSZEG: 11230
NDX: 26 OSSZEG: 10917
NDX: 27 OSSZEG: 10316
NDX: 28 OSSZEG: 9826
NDX: 29 OSSZEG: 9690
NDX: 30 OSSZEG: 9594
NDX: 31 OSSZEG: 9367
NDX: 32 OSSZEG: 8231
NDX: 33 OSSZEG: 8056
NDX: 34 OSSZEG: 7779
NDX: 35 OSSZEG: 7454
NDX: 36 OSSZEG: 6947
NDX: 37 OSSZEG: 6877
NDX: 38 OSSZEG: 6501
NDX: 39 OSSZEG: 6325
NDX: 40 OSSZEG: 6147
NDX: 41 OSSZEG: 6147
NDX: 42 OSSZEG: 6074
NDX: 43 OSSZEG: 5791
NDX: 44 OSSZEG: 4039
NDX: 45 OSSZEG: 3682
NDX: 46 OSSZEG: 3650
NDX: 47 OSSZEG: 3639
NDX: 48 OSSZEG: 3159
NDX: 49 OSSZEG: 2610
NDX: 50 OSSZEG: 2331
NDX: 51 OSSZEG: 2256
NDX: 52 OSSZEG: 2136
NDX: 53 OSSZEG: 1553
NDX: 54 OSSZEG: 1470
NDX: 55 OSSZEG: 891
NDX: 56 OSSZEG: 235DB: 27 OSSZEG: 344710
What else you gonna do on a Saturday?
-
peterszky
őstag
Igen, csak pozitív egészek (az összegek HUF értékek), ismétlés - ha egyforma értékekre gondolsz - akkor lehet benne, darabra korlát elméletben nincs, csak gyakorlati megfigyelés, hogy 50 alatti szám.
Az 1% az, hogy a megoldásban nem szerepel a rendezett sorban a legnagyobb első érték (mint ebben az esetben) és ezért elég sokat csiki-csukizik a magasabb darabszámnál.
Szoft összefüggés van (ezt már beépítettük), de nem állandó, amikor a nem állandó eset van, akkor indul a bf mód.
A megoldás egyébként:
68233
37626
31902
18548
17824
15864
14907
13956
12374
11621
11269
10316
9826
9367
8231
8056
7454
6877
6501
6325
4039
3682
3159
2256
2136
1470
891[ Szerkesztve ]
What else you gonna do on a Saturday?
-
peterszky
őstag
válasz sztanozs #8969 üzenetére
Ez nem jó, mert nem egyezik a darabszám, 27 db értékből kell kijönnie az összegnek.
"A lényeg, hogy az alábbi listában a végén látható darabszámban vegyünk ki értékeket úgy, hogy a végén látható összeg kijöjjön." - talán nem volt ez alapján teljesen egyértelmű, de akkor most pontosítottam
What else you gonna do on a Saturday?
Új hozzászólás Aktív témák
● olvasd el a téma összefoglalót!
- Windows 11
- Samsung Galaxy S23 és S23+ - ami belül van, az számít igazán
- LEGO klub
- Telekom mobilszolgáltatások
- Motoros topic
- Übergyors Samsungnak próbál látszani egy hamisított NVMe SSD
- Villanyszerelés
- Milyen belső merevlemezt vegyek?
- Assetto Corsa Competizione
- Milyen egeret válasszak?
- További aktív témák...