<p>Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags as they are. Your goal is have a distribution of apples that is as close to uniform as possible.</p>

<p>I realize this is a variation of the multiple knapsack problem but with some differences: all bags must be distributed, so some people will inevitably receive slightly more apples than their fair share while others will receive less.</p>

<p>Does this problem have a name? I am almost certain it is NP-hard, but is there a good approximate algorithm for this?</p>

CC BY-SA 3.0
2015-11-10T01:58:55.757Z
What is your definition of "as close to uniform as possible"? (I guess both $L_1$ and $L_{\infty}$ are interesting...)
usul
CC BY-SA 3.0
2015-11-10T02:15:24.113Z
That's open to interpretation - I'm actually having this problem in practice and I want to distribute a quantity as equally as possible. Possible objectives could either be the entropy of the resulting distribution (high entropy = uniform distribution), or the sum of absolute differences, i.e. $\sum_i abs(k_i - \frac{\sum_j n_j}{K})$ with $k_i$ being the number of apples person $i$ gets and $\frac{\sum_j n_j}{K}$ being the "fair" number of apples.
oceanhug
CC BY-SA 3.0
2015-11-10T04:44:38.627Z
See [partition problem](https://en.wikipedia.org/wiki/Partition_problem).
Kaveh
<approximation-algorithms><np-complete><partition-problem>
Distributing bags of apples equally
oceanhug
# Distributing bags of apples equally

(Asked by: username_0 on 2015-11-09)

Assume you have $N$ bags of apples that you want to equally distribute to $K$ people. Each bag contains $n\_i$ apples and you are not allowed to open and divide the bags; you must distribute the bags as they are. Your goal is have a distribution of apples that is as close to uniform as possible.

I realize this is a variation of the multiple knapsack problem but with some differences: all bags must be distributed, so some people will inevitably receive slightly more apples than their fair share while others will receive less.

Does this problem have a name? I am almost certain it is NP-hard, but is there a good approximate algorithm for this?

**Tags:** approximation-algorithms, np-complete, partition-problem

> **Comments:**
> **username_1**: What is your definition of "as close to uniform as possible"? (I guess both $L_1$ and $L_{\infty}$ are interesting...)  
> **username_0**: That's open to interpretation - I'm actually having this problem in practice and I want to distribute a quantity as equally as possible. Possible objectives could either be the entropy of the resulting distribution (high entropy = uniform distribution), or the sum of absolute differences, i.e. $\sum_i abs(k_i - \frac{\sum_j n_j}{K})$ with $k_i$ being the number of apples person $i$ gets and $\frac{\sum_j n_j}{K}$ being the "fair" number of apples.  
> **username_2**: See [partition problem](https://en.wikipedia.org/wiki/Partition_problem).  

---

## 0 answers

