Zaino 0/1

NP-arduo

Ci sono nn oggetti, l'oggetto jj pesa wjw_j e rende pjp_j, e uno zaino di capacità WW, tutti numeri interi. Ogni oggetto si prende intero o si lascia: xj=1x_j=1 se entra nello zaino. Si cerca il carico di profitto massimo che non supera WW.

max⁡ ∑j=1npjxjs.a. ∑j=1nwjxj≤Wxj∈{0,1}j=1,…,n\begin{aligned} \max\ & \sum_{j=1}^{n}p_jx_j\\ \text{s.a.}\ & \sum_{j=1}^{n}w_jx_j\le W\\ & x_j\in\{0,1\} && j=1,\dots,n \end{aligned}

Perché è difficile

È una PLI ed è NP-arduo. La programmazione dinamica lo risolve in O(nW)O(nW) o in O(n2pmax⁡)O(n^2p_{\max}), ma sono tempi pseudopolinomiali: WW si scrive con circa log⁡2W\log_2 W cifre, quindi O(nW)O(nW) è polinomiale nel valore di WW e non nella lunghezza dell'input.

Da ricordare

  • Il greedy per pj/wjp_j/w_j qui non garantisce l'ottimo.
  • WW piccolo: prima PD; profitti piccoli e WW grande: seconda PD; numeri grandi: Branch & Bound, con bound in O(n)O(n) per nodo.
  • Nel caso peggiore l'albero del Branch & Bound ha 2n2^n foglie.

Algoritmi

Fonti: dispensa §3.4.5 e §3.5.1, appunti Lezione 8, §1, §3, §5-7.