Hirdetés
- Xiaomi 13 - felnőni nehéz
- Fotók, videók mobillal
- Milyen okostelefont vegyek?
- Samsung Galaxy Watch8 és Watch8 Classic – lelkes hiperaktivitás
- Google Pixel topik
- Xiaomi 15T Pro - a téma nincs lezárva
- Samsung Galaxy S25 - végre van kicsi!
- 8000 nit, maradhat? A szaúdiaknál kezd a Honor 600 Pro
- Tesztkört futott a OnePlus Nord CE6
- Youtube Android alkalmazás alternatívák reklámszűréssel / videók letöltése
-
Mobilarena
Új hozzászólás Aktív témák
-
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
-
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 -
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
-
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).
-
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 -
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?
, de itt is van egy szép kis backtrack:Új hozzászólás Aktív témák
Hirdetés
● olvasd el a téma összefoglalót!
- 27% - Samsung S32DM700UU Smart M7 Monitor! 3840x2160 / 4ms / 60hz / 4K
- Iphone 16 pro max 256gb 97% ONE FÜGGŐ
- 27% - ASUS TUF Gaming VG28UQL1A Monitor! 3840x2160 / 1ms / 144Hz / G-Sync / FreeSync BeszámítOK!
- Apple iPhone 13 Mini 128GB, Kártyafüggetlen, 1 Év Garanciával
- Apple iPhone 15 Pro 128GB, Kártyafüggetlen, 1 Év Garanciával
- ÁRGARANCIA!Épített KomPhone Ryzen 5 7600X 32/64GB RAM RTX 5070 12GB GAMER PC termékbeszámítással
- Apple iPad Pro 12,9 (3. generáció) 64GB Wi-Fi + Cellular használt, karcmentes
- Lenovo Thinkpad P15 Gen 2 - 82 akkuciklus - 27% ÁFA- Garancia - 0373BE
- TOP Pure White PC /Ryzen 7 9800X3D, 32GB DDR5 RAM, 1TB M.2 PCIe SSD/ akciós áron eladó! BeszámítOK!
- MSI Thin GF63 - 15.6"FHD IPS 144Hz - i5-12450H - 8GB - 512GB - RTX 3050 4GB - Win11 - Gari - MAGYAR
Állásajánlatok
Cég: Laptopműhely Bt.
Város: Budapest