# Distributing bags of apples equally

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?

• What is your definition of "as close to uniform as possible"? (I guess both $L_1$ and $L_{\infty}$ are interesting...) – usul Nov 10 '15 at 1:58
• 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 Nov 10 '15 at 2:15
• – Kaveh Nov 10 '15 at 4:44