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?
Distributing bags of apples equally
approximation algorithms;np complete;partition problem