<p>The <a href="http://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm" rel="nofollow">first-fit algorithm</a> is a greedy algorithm that states "For each item, it attempts to place the item in the first bin that can accommodate the item".</p>

CC BY-SA 3.0
2012-08-23T22:19:36.440Z
So its 2-x approximation bound does not depend on the order of bins? Here the size of bins are different. If I use the large bins for small objects the large objects cannot be placed.
Masood_mj
CC BY-SA 3.0
2012-08-24T03:19:18.953Z
Since greedy is not necessarily optimal, why not place each object into the bin just large enough to fit it? It is still greedy and first fit with a slight heuristic .
Josh C.
CC BY-SA 3.0
2012-08-24T15:54:41.370Z
@Masood_mj I have personally implemented a first-fit packing algorithm that puts different sized objects into different sized bins. I ordered my objects from largest to smallest first and picked bins that were *just* larger than the object I was placing. It worked really well.
Josh C.
CC BY-SA 3.0
2012-08-23T19:30:12.367Z
2012-08-23T19:30:12.367Z
Josh C.
<p>I started a project under MIT license to try to solve this problem.  Currently it uses the 'best fit' approach.  Sorts 'items' from largest to smallest and sorts bins from smallest to largest.  Finds first bin that is large enough to use that has ALREADY been used (if possible).  Let's see if we can make it a good enough solution for all.</p>

<p><a href="https://github.com/asharif/packit4.me" rel="noreferrer">https://github.com/asharif/packit4.me</a></p>

CC BY-SA 3.0
2012-09-25T22:53:59.920Z
2012-09-25T22:53:59.920Z
Arash Sharif
<p>Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?</p>

<p>More formally, there are $n$ bins of size $b_i$ for $i=1,\dotsc,n$, and $m$ objects, each of size $o_j$ for $j=1,\dotsc,m$.</p>

<p>Is there a solution that can pack all of these items into the bins?</p>

CC BY-SA 3.0
2012-08-24T01:14:31.183Z
“Is there a solution that can pack all of these items into the bins?” is a decision problem, and I do not know what you mean by approximation for it.  I think that there are several natural optimization problems related to that decision problem.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-24T01:29:18.463Z
Thanks, can you refer me to any algorithm/paper that tries to solve this decision problem?
Masood_mj
CC BY-SA 3.0
2012-08-24T12:50:39.200Z
Um, brute force algorithm?  I am not familiar with advances in exponential-time algorithms.
Tsuyoshi Ito
<cc.complexity-theory><np-hardness><approximation-algorithms><packing>
Bin packing approximation with different bin sizes
Masood_mj
# Bin packing approximation with different bin sizes

(Asked by: username_0 on 2012-08-22)

Is there any greedy solution with an approximation bound for the bin-packing problem when we have bins of different size?

More formally, there are $n$ bins of size $b\_i$ for $i=1,\dotsc,n$, and $m$ objects, each of size $o\_j$ for $j=1,\dotsc,m$.

Is there a solution that can pack all of these items into the bins?

**Tags:** cc.complexity-theory, np-hardness, approximation-algorithms, packing
> **Comments:**
> **username_1**: “Is there a solution that can pack all of these items into the bins?” is a decision problem, and I do not know what you mean by approximation for it.  I think that there are several natural optimization problems related to that decision problem.  
> **username_0**: Thanks, can you refer me to any algorithm/paper that tries to solve this decision problem?  
> **username_1**: Um, brute force algorithm?  I am not familiar with advances in exponential-time algorithms.  

---

## 2 answers

### Answer by username_3 on 2012-09-25. Score: 5 | Accepted answer

I started a project under MIT license to try to solve this problem. Currently it uses the 'best fit' approach. Sorts 'items' from largest to smallest and sorts bins from smallest to largest. Finds first bin that is large enough to use that has ALREADY been used (if possible). Let's see if we can make it a good enough solution for all.

<https://github.com/asharif/packit4.me>


---

### Answer by username_2 on 2012-08-23. Score: 3

The [first-fit algorithm](http://en.wikipedia.org/wiki/Bin_packing_problem#First-fit_algorithm) is a greedy algorithm that states "For each item, it attempts to place the item in the first bin that can accommodate the item".

> **Comments:**
> **username_0**: So its 2-x approximation bound does not depend on the order of bins? Here the size of bins are different. If I use the large bins for small objects the large objects cannot be placed.  
> **username_2**: Since greedy is not necessarily optimal, why not place each object into the bin just large enough to fit it? It is still greedy and first fit with a slight heuristic .  
> **username_2**: @Masood_mj I have personally implemented a first-fit packing algorithm that puts different sized objects into different sized bins. I ordered my objects from largest to smallest first and picked bins that were *just* larger than the object I was placing. It worked really well.  

---

