Zaino frazionario

P

Ci sono nn oggetti, l'oggetto jj pesa wjw_j e rende pjp_j, e uno zaino di capacità WW. Gli oggetti si possono spezzare: xj∈[0,1]x_j\in[0,1] è la frazione dell'oggetto jj caricata. Si cerca il carico di profitto massimo che non supera WW.

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

Perché è facile

È il rilassamento continuo dello zaino 0/1, quindi una PL. Il greedy che carica gli oggetti per pj/wjp_j/w_j non crescente è esatto e costa O(nlog⁡n)O(n\log n) per l'ordinamento, O(n)O(n) se gli oggetti sono già ordinati.

Da ricordare

  • Dell'oggetto critico ss, il primo che non entra per intero, si carica xs=(W−∑j<swj)/wsx_s=(W-\sum_{j<s}w_j)/w_s; quelli dopo restano fuori.
  • La soluzione ha al più una componente frazionaria e riempie lo zaino.
  • zfrac∗≥z0/1∗z^*_{\mathrm{frac}}\ge z^*_{0/1}: è l'upper bound che il Branch & Bound usa nello zaino 0/1.

Algoritmi

Fonti: dispensa §3.4.5, appunti Lezione 8, §1-2.