Tag

NP

Browsing

Introducere O problemă cu largă aplicabilitate practică, de la încărcarea mărfurilor în camioane și planificarea activităților până la amplasarea anunțurilor în pauzele publicitare. Problema rucsacurilor Dându-se un set \(I={1,…,n}\) de obiecte cu mărimi \(s_i \in (0, 1]\), și un set \(B={1,..,k}\) de cutii cu capacitatea 1, să se găsească o aranjare a obiectelor astfel încât numărul de cutii utilizat să fie minim. Formal, să se găsească o asociere \(a : I \rightarrow B\) astfel încât…