Mi ennek az optimalizálási problémának a leggyorsabb megoldása?
Figyelt kérdés
Van N termék, mindegyikhez ismerjük a k_i árát, és tudjuk, hogy megvásárlásuk esetén p_i profitot hoz (i index 1-től N-ig). Összesen P pénzem van, amiből úgy akarok bevásárolni, hogy a lehető legnagyobb profitot kapjam.
Ha végignézem az összes bevásárlási lehetőséget, az O(2^n) lépésből áll, de biztos van ennél gyorsabb algoritmus. Esetleg ismert a problémának leggyorsabb megoldása is?
2019. márc. 19. 21:10
1/5 anonim 
válasza:
válasza:Ha jól emlékszem, a kulcsszó az operációkutatás.
2/5 anonim válasza:
válasza:"Ha végignézem az összes bevásárlási lehetőséget, az O(2^n) lépésből áll"
Gondolom itt az n=N
Tehát 1 termékből csak 1 darab van?
Konkrét algoritmus kell, vagy csak hogy milyen elméleti O(f(N)) futásidejű létezik?
3/5 A kérdező kommentje:
Konkrét algoritmus érdekelne. És igen, egy termékből egy darab van.
2019. márc. 19. 22:25
4/5 anonim válasza:
válasza:Ez a 0-1 knapsack problem és O(nP) algoritmussal megoldható. Google első találat ad kódot is.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!