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?

  • 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


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.