# Variation of bin packing

My problem is related to the standard bin packing problem, but in my case each item has a value, and the objective is to minimise the number of bins used to pack all the items PLUS the sum of the maximum value in each bucket.

Formally, given a bin $S$ of size $V$ and a list of $n$ items with sizes $a_1,\dots,a_n$ and values $v_1,\dots,v_n$ to pack, find an integer number of bins $B$ and a $B$-Partition of a set $S_1 \cup \dots \cup S_B$ of the set $\{1,\dots,n\}$ such that $\sum_{i \in S_k} a_i \leq V$ for all $k=1,\dots,B$. Such partition shoud be the one that minimises the quantity $B+\sum max_{i\in S_k}v_i$ for all $k=1,\dots,B$.

Do you know if this particular version has been studied before and if it has a good approximate solution algorithm?

• Can you state a bit more formally/specifically what your objective is? I don't quite understand it as currently written... – usul Jun 20 '14 at 23:33
• I've modified the original question with a formal explanation – Filippo Bistaffa Jun 21 '14 at 9:10