knapsotinis

„Knapsotinis“ (angl. knapsack) – tai optimizavimo uždavinys, kuriame reikia iš rinkinio daiktų, turinčių tam tikrą vertę ir svorį, pasirinkti tuos, kurie tilptų į ribotos talpos kuprinę (knapsack) ir suteiktų didžiausią bendrą vertę.

Pagrindiniai tipai:
1. 0/1 knapsack – kiekvieną daiktą galima paimti tik vieną kartą arba visai neimti.
2. Dalinis knapsack – daiktus galima dalinti (imti dalį).
3. Daugialypis knapsack – kiekvieno daikto yra kelios kopijos.

Paprastas pavyzdys (0/1 knapsack):
Kuprinės talpa: 5 kg.
Daiktai:
- A: 3 kg, vertė 60 €
- B: 2 kg, vertė 40 €
- C: 4 kg, vertė 80 €

Optimalus sprendimas: Imti daiktus B ir C (2 kg + 4 kg = 6 kg? – netelpa!), tiksliau: B ir A (2 kg + 3 kg = 5 kg, vertė 100 €) arba vien C (4 kg, vertė 80 €). Geriausia: A + B = 100 €.

Praktinis taikymas:
- Resursų paskirstymas (pvz., investicijos, krovinio pakavimas).
- Kriptografijoje, duomenų glaudinime.

Įrašas
Paaiškinimas	„Knapsotinis“ (angl. knapsack) – tai optimizavimo uždavinys, kuriame reikia iš rinkinio daiktų, turinčių tam tikrą vertę ir svorį, pasirinkti tuos, kurie tilptų į ribotos talpos kuprinę (knapsack) ir suteiktų didžiausią bendrą vertę. Pagrindiniai tipai: 1. 0/1 knapsack – kiekvieną daiktą galima paimti tik vieną kartą arba visai neimti. 2. Dalinis knapsack – daiktus galima dalinti (imti dalį). 3. Daugialypis knapsack – kiekvieno daikto yra kelios kopijos. Paprastas pavyzdys (0/1 knapsack): Kuprinės talpa: 5 kg. Daiktai: - A: 3 kg, vertė 60 € - B: 2 kg, vertė 40 € - C: 4 kg, vertė 80 € Optimalus sprendimas: Imti daiktus B ir C (2 kg + 4 kg = 6 kg? – netelpa!), tiksliau: B ir A (2 kg + 3 kg = 5 kg, vertė 100 €) arba vien C (4 kg, vertė 80 €). Geriausia: A + B = 100 €. Praktinis taikymas: - Resursų paskirstymas (pvz., investicijos, krovinio pakavimas). - Kriptografijoje, duomenų glaudinime.
	Išsaugoti

Jūsų pataisymai bus išsiųsti moderatorių peržiūrai, jei informacija tikslesnė/taisyklingesnė
ji bus patalpinta vietoj esamos.