Cuprins:
Definiție - Ce înseamnă Problema Rucsacului?
Problema cu sacul este o problemă de optimizare utilizată pentru a ilustra atât problema, cât și soluția. Acesta își derivă numele dintr-un scenariu în care unul este restricționat în numărul de articole care pot fi plasate în interiorul unui rucsac cu dimensiuni fixe. Având în vedere un set de articole cu greutăți și valori specifice, obiectivul este să obțină cât mai multă valoare în rucsac, având în vedere constrângerea în greutate a rucsacului.
Techopedia explică Problema Rucsacului
Problema cu sacul este un exemplu de problemă de optimizare combinațională, un subiect în matematică și informatică despre găsirea obiectului optim într-un set de obiecte. Aceasta este o problemă care a fost studiată de mai bine de un secol și este o problemă de exemplu folosită în mod obișnuit în optimizarea combinatorie, unde este nevoie de un obiect optim sau o soluție finită în care o căutare exhaustivă nu este posibilă. Problema poate fi găsită scenarii din lumea reală, cum ar fi alocarea resurselor în constrângeri financiare sau chiar în selectarea investițiilor și a portofoliilor. De asemenea, poate fi găsit în domenii precum matematica aplicată, teoria complexității, criptografie, combinatorică și informatică. Este ușor cea mai importantă problemă în logistică.
În problema cu un dos, articolele date au două atribute la minimum - valoarea unui element, care afectează importanța sa, și greutatea sau volumul unui element, care este aspectul său de limitare. Întrucât o căutare exhaustivă nu este posibilă, se pot rupe problemele în sub-probleme mai mici și se pot rula recursiv. Aceasta se numește o sub-structură optimă. Acest lucru se ocupă de un singur articol la un moment dat și greutatea curentă disponibilă încă în rucsac. Rezolvătorul de probleme trebuie doar să decidă dacă ia sau nu articolul pe baza greutății care poate fi acceptată în continuare. Cu toate acestea, dacă este un program, recalcularea nu este independentă și ar cauza probleme. Aici se pot aplica tehnici dinamice de programare. Soluțiile pentru fiecare sub-problemă sunt stocate astfel încât calculul ar trebui să se întâmple o singură dată.
