Hirdetés
- sziku69: Fűzzük össze a szavakat :)
- ricsi99: 6. Genes alaplap tündöklése.. kontra MS/Zintel korlátozásai.(Mehetnek a levesbe)
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- sellerbuyer: Milyen laptopot vegyek? Segítek: semmilyet!
- Luck Dragon: Asszociációs játék. :)
- ubyegon2: Airfryer XL XXL forrólevegős sütő gyakorlati tanácsok, ötletek, receptek
- sziku69: Szólánc.
- Argos: Az vagy, amit megeszel
- Geri Bátyó: Agglegénykonyha 1 – rizseshús másképp
- hcl: HP 255 G8 (250 G8) LCD csere
-
LOGOUT
Ú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
● olvasd el a téma összefoglalót!
- Vicces képek
- Multimédiás / PC-s hangfalszettek (2.0, 2.1, 5.1)
- Intel Core i5 / i7 / i9 "Alder Lake-Raptor Lake/Refresh" (LGA1700)
- iPhone-t használók OFF topikja
- Horgász topik
- Vírusirtó topic
- Windows 11
- Milyen notebookot vegyek?
- Nem tetszik pár profi eSport játékosnak, hogy Intel CPU-val kell játszaniuk
- Milyen okostelefont vegyek?
- További aktív témák...
- Enermax Liqmax III ARGB 360 (3/2 ventis) INGYEN FOXPOST
- MacBook Air M3 13.6" 8/256 100% akkumulátor
- Eladó egy oneplus 9 pro 256/12
- !!AKCIÓ!! AppleCare+ biztosítás és kiterjesztett garancia - Apple hivatalos biztosítás - Számlával
- Enermax ETS-T50 W-ARGB (Brutál hiányos+hibás alkatrésznek csakis) INGYEN FOXPOST
- Dell és HP szerver HDD caddy keretek, adapterek. Több száz darab készleten, szállítás akár másnapra
- MacBook Pro 13, 14, 15, 16, MacBook Air M1, M2 M3 M4 bill magyarosítás lézerrel / sapkacserével
- iKing.Hu - Samsung Galaxy S25 Edge Prémium dizájn, AI-élmény a zsebedben 12/512 GB
- Telefon felváráslás!! iPhone 15/iPhone 15 Plus/iPhone 15 Pro/iPhone 15 Pro Max
- Telefon felvásárlás!! Samsung Galaxy S24/Samsung Galaxy S24+/Samsung Galaxy S24 Ultra
Állásajánlatok
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest
Cég: CAMERA-PRO Hungary Kft.
Város: Budapest