1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ What is your definition of "as close to uniform as possible"? (I guess both $L_1$ and $L_{\infty}$ are interesting...) $\endgroup$
    – usul
    Nov 10, 2015 at 1:58
  • $\begingroup$ 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. $\endgroup$
    – oceanhug
    Nov 10, 2015 at 2:15
  • 1
    $\begingroup$ See partition problem. $\endgroup$
    – Kaveh
    Nov 10, 2015 at 4:44

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.