<p>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. </p>

<p>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$.</p>

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

CC BY-SA 3.0
2014-06-20T23:33:09.263Z
Can you state a bit more formally/specifically what your objective is? I don't quite understand it as currently written...
usul
CC BY-SA 3.0
2014-06-21T09:10:50.633Z
I've modified the original question with a formal explanation
Filippo Bistaffa
<packing>
Variation of bin packing
Filippo Bistaffa
# Variation of bin packing

(Asked by: username_0 on 2014-06-20)

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?

**Tags:** packing

> **Comments:**
> **username_1**: Can you state a bit more formally/specifically what your objective is? I don't quite understand it as currently written...  
> **username_0**: I've modified the original question with a formal explanation  

---

## 0 answers

