Problema rucsacului

Problema rucsacului

Prof: [Link] UIR, Rabat 2022-2023

 Prezentarea problemei

Având în vedere:
Mai multe obiecte, fiecare având o greutate ș i o valoare
O greutate maximă pentru geantă,

Obiectiv:
Ce obiecte trebuie puse în sac pentru a maximiza
valoare totală fără a depăș i greutatea maximă permisă pentru sac?

Exemple 1: Exemple 2 :
n = 4; P = 30 KG, n = 5; P = 11 KG

Obiecte 1 2 3 4 5
1 6 18 22 28

1 2 5 67
Modélisation du problème :sac à dos en variables binaires

1 ′
=
0

Funcț ia obiectiv:
maximizarea valorii totale a obiectelor din sac:

=
=1

Constrângeri :
suma greutăț ii tuturor obiectelor din rucsac trebuie să fie mai mică sau egală cu greutatea
capacitatea maximă a rucsacului:

≤
1
 Modelarea problemei

Exemple 1:
n = 4; P = 30 KG

Constrângeri :
suma greutăț ilor tuturor obiectelor din sac trebuie să fie mai mică sau egală cu greutatea
maximal al rucsacului

≤
=1

O soluț ie realizabilă este:

1 = 0, 2 = 1, 3 = 1 ș i 4 = 1

Valoarea totală conț inută în sac este egală cu 10.

Această soluț ie nu este cea mai bună:
prindeț i doar obiectele 1 ș i 2 care vor oferi o valoare totală de
11
 Rezolvarea problemei
Metodă aproximativă (algoritm lacom 1):
Exemple 1 :

Soluț ia este :
1 = 1, 2 = 1, 3= 0 et 4= 0

Valoarea totală conț inută în sac este

egal cu 11.
 Rezolvarea problemei
Metodă aproximativă (algoritm avid 1) :
Exemple 2 :
Obiecte 1 2 3 4 5
1 6 18 22 28

1 2 5 67

Soluț ia este :
1 = 1, 2 = 1, 3= 1, 4= 0ș i 5= 0

Valoarea totală conț inută în sac este

egal cu 25.

Această soluț ie nu este cea mai bună:

luaț i obiectele 3 ș i 4 care
vor oferi o valoare totală de 40
 Rezolvarea problemei
Metodă aproximativă (algoritm lacom 2):
Calculaț i raportul (vi / pi) pentru fiecare obiect i;
Sortează toate obiectele în ordine descrescătoare a acestei valori;
Sélectionnerles objets un à un dans l’ordre du tri et ajouter
obiectul selectat în rucsac, dacă greutatea maximă este respectată.
Exemple 1:

Soluț ia este :
1 = 1, 2 = 0, 3= 1ș i 4= 0

Valoarea totală conț inută în sacoș ă este egală cu 10.

Această soluț ie nu este cea mai bună:
a lua obiectele 1 ș i 2 care vor da o valoare totală de 11
 Rezolvarea problemei
Metodă aproximată (algoritm greedy 2):
Calculează raportul (vi / pi) pentru fiecare obiect i ;
Ordonează toate obiectele în ordine descrescătoare după această valoare;
Selectaț i obiectele unul câte unul în ordinea sortării ș i adăugaț i
obiectul selectat în geantă dacă greutatea maximă este respectată.
Exemple 2: Obiecte 1 2 3 4 5
Obiecte 5 4 3 2 1 1 6 18 22 28

28 22 18 6 1 1 2 5 67
7 6 5 2 1

/ 4 3,66 3,6 3 1

Soluț ia este :
1 = 1, 2 = 1, 3= 0, 4= 0 et 5= 1

Valoarea totală conț inută în sac este egală cu 35.

Această soluț ie nu este cea mai bună:
ia obiectele 3 ș i 4 care vor oferi o valoare totală de 40
 Rezolvarea problemei

Metodă exactă (soluț ie optimă):

Procedură prin separare ș i evaluare (PSE)" ramificare ș i limitare";

Solveur Excel sau a programa
Programarea dinamică.
 Rezolvarea problemei
Metoda exactă (soluț ie optimă):
Solver Excel Exemple 1

=
=1

= 0,1 ∀ = 1… , 4
 Rezolvarea problemei
Metodă exactă (soluț ie optimă):
Solver Excel Exemple 2

Obiecte 1 2 3 4 5
1 6 18 22 28

1 2 5 67

=
=1

≤
=1

= 0,1 ∀ = 1,… , 4
 Rezolvarea problemei
Metoda exactă (soluț ie optimă):
Procedura prin separare ș i evaluare (PSE)"ramură ș i limitare";
 Programare dinamică: concepte de bază
Patru entităț i de identificat

i) Întregul ansamblu de etape care posedă un anumit număr de stări;

Să presupunem o problemă descompusă în etape
ii) Ansamblul de stări corespunzător condi ț iilor posibile la început

de o etapă;
iii) Ansamblul ac ț iunilor (activită ț ilor) care se oferă agentului de decizie
(variabile de decizie);
iv) La formula de recuren ț ă
 Programare dinamică : notare
N= numărul etapelor;
n= indice al etapei curente;
= stare la începutul etapei;
= variabilă de decizie asociată etapei;
( , )= contribuț ia etapelor n, n+1,…, N la valoarea obiectivului
când ne aflăm în stare la începutul etapei, că decizia este
, ș i că deciziile optime sunt luate ulterior;
∗ = soluț ie optimă la etapă;

fn∗ (sn )= ( , ∗ = min{ ( , ) } sau max{ ( , )}

 Programare dinamică: formula de recurenț ă pentru problema rucsacului

fn∗ (sn ) va reprezenta valoarea maximă pentru un rucsac cu capacitatesn à asistenț a desn
primele obiecte.
[Link]ă un obiect lene ș apar ț ine solu ț iei optime, aceasta înseamnă că solu ț
optimală privată a celui de al n-lea obiect este de asemenea o soluț ie optimă cu un rucsac de
capacitatesn −pn.
fn∗ (sn ) =fn∗−1 (sn −pn) +vn ;

2. Ș i obiectul n-lea nu apar ț ine solu ț iei optime, asta înseamnă că

soluț ia este de asemenea o soluț ie optimă cu un rucsac de capacitatesn
fn∗ (sn ) =fn∗−1 (sn )

Putem deduce pentru tot n∈ {1, . . . , N}

Sisn < vn , aș adarfn∗ (sn ) = 0
Sinon ∗ ( )= max{ ∗ − ( ), ∗ − ( −pn) + }

Se va presupune că∀ sn ∈ {1, . . . , P}, pe un ∗ ( )=0

 Programare dinamică : Algoritm

Intrare: un ansamblu de obiecte O = {1, . . . ,N}.

Obiectul are o valoare vn ș i o greutate pn.
Sortie : un entier
1. Iniț ializaț i toate elementele tabloului T la zero.
2. Pentru orice n mergând de la 1 la N
(a) Pentru totsn allant de 1 à P
2 (a).1Ș isn < vn , aș adarfn∗ (sn ) = 0
Altfel ∗ ( )= max{ ∗ − ( ), ∗
− ( −pn) + }

Complexitatea acestui algoritm este O(NP)

Iniț ializarea tabloului se face în O(NP) operaț ii;
2. Instrucț iunea 2 (a).1 costă O(1) operaț ii.
Ș i este executată de NP ori.
 Programare dinamică : Rucsac

Etape (n) : tipuri de obiecte.

State ) : spaț iu încă disponibil la etapa.
Decizii ) :tip de obiect de pus în sac la etapă.
Formule de recurenț ă :
∗( = max{ ∗ − ( ), ∗ − ( −pn) + }

Obiecte 1 2 3 4 5
Exemple 2 : 1 6 18 22 28

1 2 5 67
 Programare dinamică: Rucsac

∗ ( = max{ ∗ ( ), ∗ ( −pn) + }
− −

Valoarea maximă este obț inută pentru ∗ ( )et este egal cu 40; Obiecte 1 2 3 4 5
1 6 18 22 28
∗( )= ∗ ( ceea ce corespunde cu a lua =0;
1 2 5 67
∗( )= ∗ ( − ) + 22 ceea ce corespunde cu a lua =1;
∗ ( )= ∗ (5− + 18 ceea ce corespunde cu a lua =1;
∗ ( )= ∗ (0) = ∗ (0)ceea ce corespunde cu a lua =0 et =0 ;

În concluzie, soluț ia optimă este următoarea:

=0 ș i =0, =1, =1 et =0 cu ∗ ( )=18+22=40.
Modelarea problemei: rucsac în variabile continue